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

2744557306

该 MATLAB 代码实现了 Dijkstra 算法，用于求解单源最短路径问题。该算法用于计算从一个节点（通常是起始节点）到其他所有节点的最短路径。下面是对代码的逐行分析和对算法思想的解释：
% I2 ^7 A7 Y1 u3 c: e9 t, M
1 \- ^. E$ @- m3 V### Dijkstra 算法的基本思想
/ g) Z' M0 s, w" X, c  q( R) i$ M3 J
Dijkstra 算法是一种贪心算法，核心思想是通过不断选择当前未访问节点中距离起点最近的节点，并更新相邻节点的最短路径估计值，最终找到所有节点的最短路径。

! ]$ r" @6 J3 X: e1 F, q代码解析

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

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

复制代码

- `a` 为权值矩阵，表示图中节点之间的边的权重。
- {# W  l, h# E+ o% _6 e7 R  S- `d` 为最短路径权重的数组。
0 g! U0 A' b0 O* d! w) K- `index1` 表示节点访问顺序。
0 k% \; O2 ]! V& Z# _% z. z- `index2` 表示节点的索引顺序。
9 |1 T8 x# H9 i2 [- Y5 F
4 H. x! }( _3 d+ A[color=rgba(6, 8, 31, 0.88)]初始化[color=rgba(6, 8, 31, 0.88)]:

1. M = max(max(a));  6 O' U! g) J2 d0 D\" N+ C/ Q
   
2. pb(1:length(a)) = 0;     % 标记所有节点为未访问  ) [* C. S; P1 b
   
3. pb(1) = 1;                % 将起点标记为已访问  7 K* T+ j* i/ g1 f/ n$ E2 d* u5 G
   
4. index1 = 1;              % 记录访问顺序  
   7 x' U1 V' J! z' P/ V8 o' m& T
5. index2 = ones(1, length(a)); % 初始化索引数组  
   3 N2 D: U5 b& X# u
6. d(1:length(a)) = M;      % 初始化距离数组为最大值  
   0 J$ N8 J, X. [% R* z
7. d(1) = 0;                % 起点到自身的距离为0  
   + U# F) Q  N$ c+ l/ j0 `: |# n3 L
8. temp = 1;                % 设定当前节点为起点

复制代码

- 通过提取权值矩阵的最大值来设置初始距离为一个很大的数（无穷大）。
* m" R* g& y# q6 s+ f+ r- `pb` 数组用于标记哪些节点已被访问。
- `d` 数组用于存储从起点到其他节点的最短路径长度，初始时将所有值设为无穷大，起点到自身的距离设为0。
) T7 o$ W  q: v& v1 N, i6 B# w
7 E% r6 ]- Q8 ]3 @. }[color=rgba(6, 8, 31, 0.88)]更新最短路径[color=rgba(6, 8, 31, 0.88)]::

1. while sum(pb) < length(a)  
   1 }8 A  ~$ Y+ J+ |& j
2.     tb = find(pb == 0);   % 找到所有未访问的节点  ! Y* m( D% V* {7 B) v0 O% x
   
3.     d(tb) = min(d(tb), d(temp) + a(temp, tb)); % 更新这些节点的距离  * h! ~+ p# C1 \& m
   
4.     tmpb = find(d(tb) == min(d(tb))); % 找到距离最小的未访问节点  
   : F( i8 j4 [9 {/ N9 j) G
5.     temp = tb(tmpb(1));   % 选择距离最小的那个节点  
   3 A* s! D/ Q( k( v! l8 ^& e
6.     pb(temp) = 1;         % 将其标记为已访问  1 t3 w: @- \. p4 l5 `
   
7.     index1 = [index1, temp]; % 记录访问顺序

复制代码

- 使用 `while` 循环遍历所有节点，直至所有节点都被访问。
( [) ?* o6 U6 j4 M2 b, J- 找到当前未访问节点 `tb`，并更新这些节点的最短路径长度。
' C9 V4 Y; J# L  w- 选择距离最小的未访问节点来作为下一个要访问的节点。
- 将该节点标记为已访问，并记录访问顺序。

1 w2 y# J3 J+ _( A/ ?9 V7 S[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)));   
   / L' e: e1 R6 k4 V4 k
2. if length(index) >= 2  
   6 d0 U$ H& ~, e- ^0 Q9 A  e
3.     index = index(1);  
   3 ^: V0 K* I: M! R9 l
4. end  
   $ U/ n  Q! A7 A
5. index2(temp) = index;  % 将更新后的索引存入 index2

复制代码

- 通过计算当前节点与已访问节点的关系来更新节点索引 `index2`，确保最短路径的方向正确。
. C( Y# S9 p5 K/ C/ g. z
- O5 s: ^, q2 n  `3 F总结最后，该算法实现了 Dijkstra 最短路径算法的基本逻辑：

1. 初始化距离和访问标记。
# H# }$ [( s$ n* r/ h" Z. G2. 循环获取离起点最近的未访问节点，并更新其邻接节点的最短路径。
' d" O4 l; |  P. e4 g0 B3. 重复这一过程，直到所有节点均被访问。
" M) J  _% F& L+ f' ?6 W! J
6 |, r9 d- A5 _* p4 \, I) L最终返回的 `d` 是从起点到其他节点的最短路径长度数组，`index1` 是访问顺序，`index2` 是节点的索引顺序。这个算法的时间复杂度为 \(O(V^2)\)，其中 \(V\) 是图中节点的数量。但在使用优先队列等数据结构优化时，可以将复杂度降低到 \(O((V + E) \log V)\)，\(E\) 是边的数量。
* f- Y2 b5 P" [
" R  u. j2 \3 Z2 O( x3 `% c4 }* f
( e: [) A, a  r* V: ?9 {! j5 E& ~