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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
, q& E7 `% r; t, l' Q' `
2,0,inf,3,3,1,inf;8 \) C r- @& w) S+ w# B) H. X
4,inf,0,2,3,1,inf;
* Q/ [: l- ?/ I' U# p
inf,3,2,0,inf,inf,1; 3 {) F( {* `( |
inf,3,3,inf,0,inf,3;
' {% X; j5 a$ I( s) I9 o1 N
inf,1,1,inf,inf,0,4;
( t$ D8 q ^ [1 R! V2 f
inf,inf,inf,1,3,4,0];
, C+ J# H! z0 `4 A8 V8 Z
n=size(w,1); % n记录图中点数5 H, p7 @. ^) j\" q
D=w; % D为距离矩阵
5 T& J) ?\" \. D9 c
R=[]; % R为路径矩阵6 S9 h. [! f8 k0 b0 P5 L
6 o8 m3 U, E' D* m5 ^: m& |
for i=1:n: Q7 ~) C: ?6 @) U o2 z- `
for j=1:n- w- d( ~( ?6 C# f- Q/ S5 I# Y
R(i,j)=j; % 为R矩阵赋初值8 A; p7 b* Q# e6 t. X1 }
end
* b) x/ ?+ f b' r8 g
end# N# h4 [8 P' e2 s
) e0 n& E' s$ k& ^: [+ [' L2 Y; A
for k=1:n % k3 @7 }6 I& O, P# @
for i=1:n
\" ^- \- ?6 M8 u' w+ R
for j=1:n
* q2 s; h( I( N5 q$ i& R
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
7 o% w8 y( t: ?
D(i,j)=D(i,k)+D(k,j);9 q* ~1 T5 T& H. O; i/ K+ l
R(i,j)=k;/ w9 E$ X& y\" w
end+ h- l+ W5 x\" K( M5 g
end
+ g4 i* f4 }& p5 s4 v
end
S8 a t, H; Q! ^
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 的最短路径上的中间顶点。