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

[复制链接]

字体大小: 正常放大

2744557306

1198 主题	4 听众	2978 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; 4 O! V3 R5 q) K) F; q, s\" ]
2,0,inf,3,3,1,inf;: R% s2 A& x0 B0 ?
4,inf,0,2,3,1,inf;
8 O/ [\" `4 i. r
inf,3,2,0,inf,inf,1;
1 i$ R( j+ }& ~
inf,3,3,inf,0,inf,3;
& @9 Y) O, u5 w5 V. ?; \8 C
inf,1,1,inf,inf,0,4;! ^: E* s4 N/ r
inf,inf,inf,1,3,4,0];
- {- q; Q. P% x9 }4 | |
n=size(w,1); % n记录图中点数
. q9 Z& r& |/ `; E0 ^
D=w; % D为距离矩阵
* T$ t R+ n, y4 a% a( o0 k
R=[]; % R为路径矩阵% X$ c0 X( B0 K2 N2 Y0 c
* c\" c' n% S5 T) a: Y
for i=1:n0 U m: `# H: x. l0 s d
for j=1:n
' D+ ]# P( M# p& ^9 L7 X9 U9 O2 b
R(i,j)=j; % 为R矩阵赋初值& y/ {# \5 G) D5 L
end
7 E! q7 x' @: N2 }, M6 Z; W( R
end
0 P0 r* _0 C9 b1 l* C
: H5 H- `7 `, Q8 i7 l
for k=1:n , U\" N. m' x. J# H; E; \$ m+ C
for i=1:n
# {% N* U c! \# Z# Y4 I8 A+ F% V
for j=1:n* X+ [5 A, |; q1 U6 k2 c6 p. t
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
/ B9 ~3 c& g. W\" f
D(i,j)=D(i,k)+D(k,j);# y) s) O, Q8 o4 S
R(i,j)=k;
2 q0 T4 N- x( A, B) \3 b\" ~\" ^% J3 N
end\" ~6 |& A( T1 M* Q0 u/ C# d
end3 Q, p( q% x; Q' b1 P) _- P) x( b
end
% w+ M' `* f. C' O2 ^% v- b
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 的最短路径上的中间顶点。