Dijkstra算法求c1点到其余各点的最短路径

2744557306

该 MATLAB 代码实现了 Dijkstra 算法，用于求解单源最短路径问题。该算法用于计算从一个节点（通常是起始节点）到其他所有节点的最短路径。下面是对代码的逐行分析和对算法思想的解释：
" M+ L  d. d4 {8 J, R7 k, s
- y0 i0 f! O7 I0 l1 p### Dijkstra 算法的基本思想
6 L/ T4 x3 q3 l- h
' w* M6 s4 h5 |* _" U! k$ TDijkstra 算法是一种贪心算法，核心思想是通过不断选择当前未访问节点中距离起点最近的节点，并更新相邻节点的最短路径估计值，最终找到所有节点的最短路径。

代码解析

[color=rgba(6, 8, 31, 0.88)]函数定义:

1. function [d, index1, index2] = dijkf(a)

复制代码

- `a` 为权值矩阵，表示图中节点之间的边的权重。
& Q& G3 f1 n6 N6 I$ D8 V- `d` 为最短路径权重的数组。
- `index1` 表示节点访问顺序。
8 h1 N- _; U' \& Z6 P2 h) X- `index2` 表示节点的索引顺序。

9 k! o9 T9 U9 N% q( C6 }& _& c[color=rgba(6, 8, 31, 0.88)]初始化[color=rgba(6, 8, 31, 0.88)]:

1. M = max(max(a));  : j: J0 |3 l$ B7 g+ w. L
   
2. pb(1:length(a)) = 0;     % 标记所有节点为未访问  
   5 ], @8 E! t( ^8 L% c3 A( M% V
3. pb(1) = 1;                % 将起点标记为已访问  % n4 N9 S& r9 X
   
4. index1 = 1;              % 记录访问顺序  - ^2 O) [; K1 D1 ?9 W5 O
   
5. index2 = ones(1, length(a)); % 初始化索引数组  
   ; N, K* r$ |- ]: e
6. d(1:length(a)) = M;      % 初始化距离数组为最大值  8 j5 j$ R2 t& F3 x# O
   
7. d(1) = 0;                % 起点到自身的距离为0  
   1 e. d6 X+ V* d2 S4 s- k
8. temp = 1;                % 设定当前节点为起点

复制代码

- 通过提取权值矩阵的最大值来设置初始距离为一个很大的数（无穷大）。
# c) u* u9 }4 p1 z( ]4 w- `pb` 数组用于标记哪些节点已被访问。
- `d` 数组用于存储从起点到其他节点的最短路径长度，初始时将所有值设为无穷大，起点到自身的距离设为0。
# G6 n( a5 R" p) l+ f: M6 L7 i3 C+ l( Y
) ~0 m- b  ]9 ^, L, ~7 h$ s[color=rgba(6, 8, 31, 0.88)]更新最短路径[color=rgba(6, 8, 31, 0.88)]::

1. while sum(pb) < length(a)  & R/ w# [1 ~8 m0 x; C  c1 ]
   
2.     tb = find(pb == 0);   % 找到所有未访问的节点  ! j7 i\" j2 x% M; b
   
3.     d(tb) = min(d(tb), d(temp) + a(temp, tb)); % 更新这些节点的距离  
   1 j4 I, d' h6 p1 g
4.     tmpb = find(d(tb) == min(d(tb))); % 找到距离最小的未访问节点  ! M5 N- W$ ^: Y# s: R( \# \
   
5.     temp = tb(tmpb(1));   % 选择距离最小的那个节点  
   1 w. L0 ]9 P6 w
6.     pb(temp) = 1;         % 将其标记为已访问  
   9 h8 [) _2 m3 f4 V# T2 H3 O  E' d
7.     index1 = [index1, temp]; % 记录访问顺序

复制代码

- 使用 `while` 循环遍历所有节点，直至所有节点都被访问。
) f. Y+ d1 Z5 ?: @) R. Y6 a* ]- 找到当前未访问节点 `tb`，并更新这些节点的最短路径长度。
0 x' ~% T" F# x) t; B1 x. r- 选择距离最小的未访问节点来作为下一个要访问的节点。
/ Z4 a( h; _1 a- y! e- 将该节点标记为已访问，并记录访问顺序。
$ F# o" q' [# \' h  e
[color=rgba(6, 8, 31, 0.88)]记录顺序和索引[color=rgba(6, 8, 31, 0.88)]:

1. index = index1(find(d(index1) == d(temp) - a(temp, index1)));   # y6 W) h8 W  `* [7 b$ B9 n\" x
   
2. if length(index) >= 2  
   ; U( O3 X. b5 ^4 S  v  [
3.     index = index(1);  
   1 ?/ K; N( x/ B; l  w2 h( V) C9 V( T
4. end  
   + R, N7 ~/ x2 H6 |/ l' G9 V
5. index2(temp) = index;  % 将更新后的索引存入 index2

复制代码

- 通过计算当前节点与已访问节点的关系来更新节点索引 `index2`，确保最短路径的方向正确。

# `. j* U; M' W& ~* i0 o总结最后，该算法实现了 Dijkstra 最短路径算法的基本逻辑：
  ~0 p  Q* q* \7 `; h
1. 初始化距离和访问标记。
$ K9 A9 Y5 J: ^2. 循环获取离起点最近的未访问节点，并更新其邻接节点的最短路径。
0 R( b0 ]6 j- J1 d8 t& ~/ b# s! }  z; q3. 重复这一过程，直到所有节点均被访问。

最终返回的 `d` 是从起点到其他节点的最短路径长度数组，`index1` 是访问顺序，`index2` 是节点的索引顺序。这个算法的时间复杂度为 \(O(V^2)\)，其中 \(V\) 是图中节点的数量。但在使用优先队列等数据结构优化时，可以将复杂度降低到 \(O((V + E) \log V)\)，\(E\) 是边的数量。
+ x# G, ~; j2 Y$ u1 z2 h: ^


6 f5 @" R/ R0 S% i+ C, k