Floyd算法求两点间的最短路

2744557306

MATLAB 代码实现了一种计算图中两个节点之间最短路径的算法。它利用了 Floyd-Warshall 算法的思想来逐步更新路径长度，并在此基础上求解最短路径。下面逐步分析其功能和实现细节。
, ^/ R& w9 F0 p& L函数定义

1. function [P, u] = n2shorf(W, k1, k2)

复制代码

- `W` 是输入的邻接矩阵，表示图中节点间的权重（距离）。
- `k1` 和 `k2` 分别表示起始节点和目标节点的索引。
- 输出 `P` 为从 `k1` 到 `k2` 的最短路径，`u` 为最短路径长度。
初始化

1. n = length(W); % 获取图中节点的数量  # ~. J' B( i; b# |) G* F5 \- ]
   
2. U = W;         % 用 U 保存当前的路径长度  , _9 Y3 \2 I\" s5 w8 T  b  G. G
   
3. m = 1;        % 初始化步数

复制代码

- `n` 是节点总数。
- `U` 初始化为邻接矩阵 `W`，用于存储更新后的最短路径长度。
$ A8 C  e+ L: ]1 p& a- `m` 控制外层循环的索引。
0 K+ B- X, \  w7 T1 F9 j9 T主程序

1. while m <= n  
   1 e! P1 u* M% f( i; h, L6 i! X
2.     for i = 1:n  
   0 T\" R; R8 X6 b\" V
3.         for j = 1:n  3 ~) D  F! k1 F9 o
   
4.             if U(i,j) > U(i,m) + U(m,j)  
   1 m% d5 b9 R, I+ M
5.                 U(i,j) = U(i,m) + U(m,j);  
   ' t$ Q% _- ~0 q0 u+ |, x& L
6.             end  
   6 m6 Y( i- x( `4 S1 Y6 Z( m  ~
7.         end  
   * E* R\" [( f* H4 r& E8 C\" B
8.     end  $ p, u+ y; n0 S2 V
   
9.     m = m + 1;  
   ) x5 w, [. P$ v) c
10. end

复制代码

- 外层 `while` 循环运行 `n` 次（节点数量），内层嵌套的 `for` 循环遍历所有节点对 `(i, j)`。
- 如果通过节点 `m` 的路径长度比当前已知的 `U(i, j)` 更短，则更新 `U(i, j)`。
6 ^, X! R3 ]4 i- 这段代码的作用正是计算任意两个节点之间的最短路径，最终更新的 `U` 矩阵将保存所有节点之间的最短距离。
获取最短路径长度

1. u = U(k1, k2);

复制代码

- 通过访问 `U(k1, k2)` 获取从 `k1` 到 `k2` 的最短路径长度。
求解最短路径

1. P1 = zeros(1, n);  
   2 d8 Z/ f; f1 L- l
2. k = 1;  & t: ^! H9 u! N$ J9 v! R
   
3. P1(k) = k2; % 将目标节点放入路径中  
   : S) H; m1 {; \& j
4. V = ones(1, n) * inf; % 初始化路径计算辅助数组  
   # h2 t* u) q/ E! d
5. kk = k2; % 当前节点设置为目标节点

复制代码

- `P1` 用于存储从 `k2` 回溯到 `k1` 的路径，初始化为全零数组。
' L% B( x, h! {& u9 T- `V` 用于保存路径长度的一种中间表示。
/ z7 ?+ Q# O& y, ]
[color=rgba(0, 0, 0, 0.96)]
: l' ^+ L9 j  M+ b2 q9 f6 H! i回溯路径[backcolor=rgb(36 38 52 / var(--tw-bg-opacity))]

1. while kk ~= k1  
   : |0 b( L( l2 W  |* M% V: }- Z
2.     for i = 1:n  * O3 {# U5 W- x3 M6 u& k
   
3.         V(1, i) = U(k1, kk) - W(i, kk);  ; I1 D3 j& t! N1 R. x5 v
   
4.         if V(1, i) == U(k1, i)  . I7 W0 y! f+ ?) l  y, [
   
5.             P1(k + 1) = i;  
   4 F9 L+ `. {$ }
6.             kk = i; % 更新当前节点为前驱节点  
   . x4 t8 Q* T( b( f\" A
7.             k = k + 1;  
   9 _1 G1 q\" F* _& o
8.         end  
   4 _7 \; S% B0 U* z4 _
9.     end  
   / W% q7 ~  M. W$ G
10. end

复制代码

• 通过回溯来确定路径。根据当前节点 kk 的前驱节点逐步回溯，直到找到起点 k1。
• 在内循环中计算 V 数组，能否从 k1 经过某一节点 i 到达 kk。
  

完成路径[backcolor=rgb(36 38 52 / var(--tw-bg-opacity))]
6 w* N0 k& Z# @4 A

1. k = 1;  
   ) ~! @3 Y1 b0 A
2. wrow = find(P1 ~= 0); % 获取所有非零节点的索引  \" l% G' d8 e4 w) x! g4 f3 G
   
3. for j = length(wrow):-1:1  + ~: E2 f( W' u, G
   
4.     P(k) = P1(wrow(j));  9 A# w% R2 T  n* t
   
5.     k = k + 1;  
   ) O$ L& M, U$ w\" r
6. end  7 Z% }0 [) i+ e3 W% J
   
7. P;

复制代码

• 提取路径 P，通过从 P1 中回溯找到从 k1 到 k2 的顺序。
• 注意这里是从后往前填充路径，确保路径顺序是正确的。
  

总结

[color=rgba(6, 8, 31, 0.88)]整体而言，n2shorf 函数实现了计算从节点 k1 到节点 k2 间的最短路径及其长度的功能，使用了 Floyd-Warshall 算法来更新路径长度，并通过回溯确定具体的路径。这种方法适用于计算任意两个节点之间的最短路径，但可能在时间复杂度 �(�3)O(n3) 的图中对于较大的图处理时效率较低。

[color=rgba(0, 0, 0, 0.96)]


5 r, W* S9 Z, E7 }) _3 d[color=rgba(0, 0, 0, 0.96)][backcolor=var(--sds-color-grey-layer3-normal, #ffffff)]


. e1 t% i0 W" t# A3 d