查看: 1376|回复: 0

Floyd算法求两点间的最短路

字体大小: 正常放大

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

发表于 2024-10-23 16:47 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

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

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

复制代码

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

n = length(W); % 获取图中节点的数量
7 h- j: f3 r$ t Y. o W1 |
U = W; % 用 U 保存当前的路径长度
( x\" w& `% d, p& b6 _% W5 Y
m = 1; % 初始化步数

复制代码

- `n` 是节点总数。
- `U` 初始化为邻接矩阵 `W`，用于存储更新后的最短路径长度。
- `m` 控制外层循环的索引。
主程序

while m <= n
6 E, J' b\" a3 G9 w! E% W2 \* m
for i = 1:n 3 h6 ^ [6 D7 _
for j = 1:n
, h+ D3 e# o' D4 E\" t
if U(i,j) > U(i,m) + U(m,j) * Y; N9 d1 z/ j8 c) @3 `4 X
U(i,j) = U(i,m) + U(m,j);
( B7 b/ ]$ m9 a9 N; _7 P
end
' \# R1 n) A* N* F: f7 S- T
end
; i3 v% S/ S% ~6 C, ~
end
( O; A/ }; L- h) [! ]9 M& Z5 p, ]
m = m + 1; ' v+ q( F% E0 z' h$ k
end

复制代码

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

u = U(k1, k2);

复制代码

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

P1 = zeros(1, n); , T\" {2 t8 v. c6 a, F9 c\" j
k = 1;
; l1 h6 V# J' \# t+ i
P1(k) = k2; % 将目标节点放入路径中 8 f. H& a. A* Z# V2 l
V = ones(1, n) * inf; % 初始化路径计算辅助数组 . I' T u$ c* d( n r) X6 t
kk = k2; % 当前节点设置为目标节点

复制代码

- `P1` 用于存储从 `k2` 回溯到 `k1` 的路径，初始化为全零数组。
- `V` 用于保存路径长度的一种中间表示。

[color=rgba(0, 0, 0, 0.96)]
回溯路径[backcolor=rgb(36 38 52 / var(--tw-bg-opacity))]

while kk ~= k1 # q1 c6 @& J6 d V! c
for i = 1:n . ~5 x$ C4 B, v5 E1 M
V(1, i) = U(k1, kk) - W(i, kk); 2 ?% c% d, q# R4 ]3 g
if V(1, i) == U(k1, i)
5 F\" u M1 ]* y Q, p4 ]+ s9 J5 b
P1(k + 1) = i;
0 f2 R/ n# q1 u7 [% k& P1 a n\" s
kk = i; % 更新当前节点为前驱节点
; B& z9 e* z- ?# }9 W0 `: l: e
k = k + 1; 4 c# q. r) i$ _: J% O
end
5 o2 d' ?2 Y: H\" x3 u1 l
end
# Z: E% \, h1 O8 ]5 b# S$ @) Z
end

复制代码

通过回溯来确定路径。根据当前节点 kk 的前驱节点逐步回溯，直到找到起点 k1。
在内循环中计算 V 数组，能否从 k1 经过某一节点 i 到达 kk。
4 s0 R! P. {3 C; D0 v" l' v

完成路径[backcolor=rgb(36 38 52 / var(--tw-bg-opacity))]

k = 1;
\" z8 I V) g: v m% u
wrow = find(P1 ~= 0); % 获取所有非零节点的索引 7 F3 w9 }( L0 _4 g/ K+ |\" q
for j = length(wrow):-1:1
7 E7 }; s$ S- T5 E
P(k) = P1(wrow(j));
4 {1 q! [1 P\" ], N, B+ t
k = k + 1; 3 u4 M+ _( Q4 } o
end
+ R8 @! U4 ]# m) H6 Z( @# l
P;

复制代码

提取路径 P，通过从 P1 中回溯找到从 k1 到 k2 的顺序。
注意这里是从后往前填充路径，确保路径顺序是正确的。
6 \; V' n5 R! c0 ]0 E# e

总结

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

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

[color=rgba(0, 0, 0, 0.96)][backcolor=var(--sds-color-grey-layer3-normal, #ffffff)]