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

[复制链接]

字体大小: 正常放大

2744557306

1176 主题	4 听众	2884 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
\" ?& i8 O, s1 I
2,0,inf,3,3,1,inf;) u$ d5 A$ ~# i+ f' j- I1 B$ N, d
4,inf,0,2,3,1,inf; % h4 E: b; n5 o* A$ m
inf,3,2,0,inf,inf,1; 4 u) I& s* y3 @6 d' v
inf,3,3,inf,0,inf,3;
$ y2 {- F. C( l) O i
inf,1,1,inf,inf,0,4;# `6 s, m& c9 |) ~
inf,inf,inf,1,3,4,0];
3 L Q. ^* ~# i& G
n=size(w,1); % n记录图中点数
6 R3 \5 \( L* H& {
D=w; % D为距离矩阵% _; A! R+ V# P( J) M @5 x
R=[]; % R为路径矩阵1 Q1 q) S* e\" d\" a* |$ p
: v- ]0 x3 Y$ ?
for i=1:n- |; s* Z. ]2 [' |- E2 I# n. v
for j=1:n5 E! K* F, [1 @2 X- G/ z$ v) I8 F
R(i,j)=j; % 为R矩阵赋初值- I! X3 g! k7 R
end
( |, l' i: ]( _2 a$ A
end
\" d\" N) Y6 m0 ~- ^$ J: g' W\" i+ x& I
% G. E3 x! h, q& _5 Y- B
for k=1:n
7 N% m4 E7 Y# _+ G
for i=1:n
7 s; G% C9 x2 J- _6 J4 A
for j=1:n `2 F; O2 |1 R# I. N$ s7 \; S
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 / m+ G, g\" J, ^/ ~6 z& v
D(i,j)=D(i,k)+D(k,j);( h! |2 t! ?) [* k4 |1 O. [; c2 T
R(i,j)=k;; J. [ l! X o9 n3 I: e
end% `\" a6 s! @, Z) B2 K
end
- n( W& v$ Y: }0 P5 i
end& p7 R# T7 n9 z+ Z: d
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 的最短路径上的中间顶点。