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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
1 @4 A; P d# G- Y\" C
2,0,inf,3,3,1,inf;
$ _% _6 E4 _: U. f8 g9 j
4,inf,0,2,3,1,inf;
1 q: S4 p- B# |9 z3 D* P2 ]1 C
inf,3,2,0,inf,inf,1;
% H! I1 R, A+ g W5 Q
inf,3,3,inf,0,inf,3;' X% ~\" r3 d- m; w4 d
inf,1,1,inf,inf,0,4;' |+ ?: L L# R3 Y: c- g\" X5 L
inf,inf,inf,1,3,4,0];
& m! i2 i/ u: S4 w. z# _$ M% G
n=size(w,1); % n记录图中点数 {7 j. r8 g) J$ m
D=w; % D为距离矩阵9 o1 i- @% _6 q _) |& Q* {
R=[]; % R为路径矩阵6 E6 x\" t3 B$ C' D! L y; _
1 U0 X9 z# M7 c8 z. e( N! j5 I
for i=1:n+ j4 {3 X0 f: d! v4 ~0 A1 U
for j=1:n/ V8 I2 T' r6 r& T4 o) |) X& m, L
R(i,j)=j; % 为R矩阵赋初值
# a6 w5 ~4 O9 j, j, h* m6 k
end5 _! g, A* d8 c) `: W/ F6 D
end
4 z- U; X8 `) b3 }. u1 J6 z8 Y% ^) X% g
4 c0 _6 N. x+ U* n/ ?
for k=1:n ; y; g\" T1 P) j! W$ U9 J
for i=1:n\" a2 u# n P. \+ z, I
for j=1:n$ g& s7 v3 L% R' W
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
& ]' |/ R/ O* B0 ^4 i6 O% `, P
D(i,j)=D(i,k)+D(k,j);: ?0 X* y. s* `) r6 W
R(i,j)=k;
}0 Q4 \' ^5 e. v5 J
end# X- D5 r3 |- W) U* n# F6 `6 n( L
end
; ?: M+ H% ?\" ?9 z9 K5 [
end- R7 k) {1 a/ H. e0 W$ b9 Z( Z
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 的最短路径上的中间顶点。