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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
/ m& l. W/ p* o/ W0 r% ^
2,0,inf,3,3,1,inf;0 ]3 ~8 ^8 o, v- k
4,inf,0,2,3,1,inf; % v8 {2 L; i1 i1 G7 H f5 s8 t% K
inf,3,2,0,inf,inf,1;
0 }9 p7 I* j5 `' O; t
inf,3,3,inf,0,inf,3;
* M) h7 h9 P4 e
inf,1,1,inf,inf,0,4;3 \7 i\" p. p. r P# i\" z6 r! w
inf,inf,inf,1,3,4,0];; a! f, z: e s' z4 z5 `* L: T1 U) W3 Y
n=size(w,1); % n记录图中点数3 Y. C\" j4 A) B\" n
D=w; % D为距离矩阵# k% P9 @$ M8 i7 Y! U
R=[]; % R为路径矩阵
' P6 _/ f) K$ I% t6 n3 ]
4 @! M3 g( }: i) K7 E9 i# m
for i=1:n
3 q! o/ b7 r5 B7 t2 B
for j=1:n4 R! Q3 x2 g! S' r( u5 Y
R(i,j)=j; % 为R矩阵赋初值0 {5 f6 o! r. m. ]0 s0 N' H+ Y
end
+ |* z% D. S1 o b! v
end
! Q6 u# M0 g6 }+ {$ j7 e5 Z1 K4 B
6 L* R# ?) u* v. ~* L# k& b
for k=1:n & h8 o\" u8 C5 q0 g( o) t
for i=1:n
0 ]* _ f8 g2 o
for j=1:n' u/ i- ~\" H: B5 Y0 C; t# u
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
7 a7 o. H7 k% a* O3 _+ }) t& W+ \
D(i,j)=D(i,k)+D(k,j);5 ?7 l* ^5 g( y
R(i,j)=k;
7 @* k- ]+ i; E6 c& S0 P+ Y\" l2 K8 g
end+ R- D6 T8 ~- n! e, W
end
4 R0 [4 c$ A7 | [) n# q
end: ~5 c! i2 ?& k9 k
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 的最短路径上的中间顶点。