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

[复制链接]

字体大小: 正常放大

2744557306

1176 主题	4 听众	2884 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
4 W! j1 }- t0 w1 k0 U4 M
2,0,inf,3,3,1,inf;/ h o O% B' _: j
4,inf,0,2,3,1,inf;
: {: D, G) p8 R% R& v% J3 [
inf,3,2,0,inf,inf,1;
5 _5 U+ T# [9 G\" r7 d% a1 w
inf,3,3,inf,0,inf,3;
# ~\" w) O6 b0 Z7 L# N5 r* Q* w
inf,1,1,inf,inf,0,4;' H/ K2 u- C( E1 p' Y$ w
inf,inf,inf,1,3,4,0];
% V# V; J s- Z; F9 T3 X( X# d, E
n=size(w,1); % n记录图中点数4 t6 d( {; m& O7 y6 {
D=w; % D为距离矩阵# f! X) ?8 E1 A! ?$ \+ ?
R=[]; % R为路径矩阵
, X! b, R( S6 D |$ P9 Q) h% y, {
3 p% T' _: K* L8 m x. e) j$ q
for i=1:n. g* F( ~5 l* z# p' U# Q9 X
for j=1:n! u% `4 e0 Y0 g0 s W8 N, I
R(i,j)=j; % 为R矩阵赋初值4 c: g c. d9 Q- A- g! Q
end# Q- N+ N! M5 y' N3 h
end. P% \7 I- y$ c5 [8 S5 D9 ^
8 W6 \$ J/ {% P+ C# n
for k=1:n
9 V! R. Z; [# l# M4 R( q
for i=1:n& l# z8 l9 h+ K0 Q
for j=1:n6 u7 _0 n9 P* S2 w, k
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 9 r% ^- P/ y) K( l: L
D(i,j)=D(i,k)+D(k,j);
% R5 I e: H. G% o3 {
R(i,j)=k;
: c: l/ d6 X+ o6 S g( b6 \ d
end1 \, t& T! U) O Y4 c6 S
end
: ~4 o$ ~6 a/ |& _\" b, }\" U
end
( A# |; ]( z% a* Q8 }- S5 w
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 的最短路径上的中间顶点。