Ford 算法来找到源点到其他各点的最短路径

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

发表于 2023-12-22 10:03 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

这段代码是Floyd-Warshall算法的一个实现，用于在带权图中找到所有顶点对之间的最短路径。让我逐步解释每一部分：
% 邻接矩阵(点与点的关系)

w=[0,2,4,inf,inf,inf,inf;
, ?; T- t5 M6 t) x5 M1 Q& J
2,0,inf,3,3,1,inf;3 Y9 a* S0 S/ O% m) H, ?: k& b
4,inf,0,2,3,1,inf; ' s4 [, R, R6 {( P+ H; J/ x& r
inf,3,2,0,inf,inf,1;
\" g1 H5 C/ j% h9 o2 ^
inf,3,3,inf,0,inf,3; b# p# {/ g# e) U$ z
inf,1,1,inf,inf,0,4;
: z' ^, f; L( D4 x/ l+ I\" G+ s
inf,inf,inf,1,3,4,0];0 G; J! J- B3 x% D1 ~5 g; ~7 Y7 [
n=size(w,1); % n记录图中点数; e$ |% e/ o! |2 a0 c
D=w; % D为距离矩阵
6 U( m& l |: `- Z& {2 W
R=[]; % R为路径矩阵: m- a6 d w, G( x& p! Q+ Q5 R, L
3 r- V8 v* Y0 ]; t
for i=1:n
- w3 k( \3 d4 S6 U; t1 ?- a
for j=1:n$ H3 g( u% T& R2 J1 N+ }
R(i,j)=j; % 为R矩阵赋初值
: a) v- {# T) q6 f# e
end
. ^0 Q- |* j6 I9 H# Z( L+ j
end
) F! C6 ^+ L# i( _3 O' D
3 c ?# K7 w, D' x& Z# p* x, D- n
for k=1:n
$ \6 q: E\" @/ }& u- l, Z
for i=1:n
# e( s1 _, l0 V) i
for j=1:n\" m, J+ _5 d4 }\" w\" I+ e
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
0 h/ ?: T1 j3 n5 w6 Y+ J
D(i,j)=D(i,k)+D(k,j);
, Z1 t5 z9 t0 Q) m0 A& q3 @; S
R(i,j)=k;# `# a' ~& A2 A ?8 X
end
+ m; L/ i\" R- q; m( k
end) D+ C* `) ?: _( g W
end
8 ^/ [4 ~+ i$ q1 L; Y
end

复制代码

D % 输出距离矩阵
R % 输出路径矩阵

解释：

1.带权图的表示：给定图被表示为邻接矩阵 w，其中 w(i, j) 表示从顶点 i 到顶点 j 的边的权重。inf 用于表示两个顶点之间没有直接的边。
2.初始化：距离矩阵 D 被初始化为与邻接矩阵相同的值。路径矩阵 R 被初始化为一个矩阵，其中每个元素 R(i, j) 最初被设置为 j。
3.Floyd-Warshall算法：嵌套循环实现了Floyd-Warshall算法。外层循环 (k) 代表通过哪个中间顶点进行路径检查。内层循环 (i 和 j) 遍历所有顶点对，并检查通过 k 从 i 到 j 的路径是否比直接从 i 到 j 的路径更短。如果是这样，就更新距离矩阵 D 和路径矩阵 R。
4.输出：最终的距离矩阵 D 和路径矩阵 R 被显示。

输出包含最终的距离矩阵和表示路径的矩阵。元素 D(i, j) 表示从顶点 i 到顶点 j 的最短距离，而 R(i, j) 表示从 i 到 j 的最短路径上的中间顶点。