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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; + c6 {6 E; p% z5 h/ h- W& d6 K8 e0 Q( N: B
2,0,inf,3,3,1,inf;
4 f: ~6 v; m s# n
4,inf,0,2,3,1,inf; ' K! d8 S x! { F/ s
inf,3,2,0,inf,inf,1;
1 U1 `5 }$ e5 n
inf,3,3,inf,0,inf,3;1 E: t) j, D* e8 I! L\" |! j5 v, \8 R
inf,1,1,inf,inf,0,4;5 m/ f: u. K4 }
inf,inf,inf,1,3,4,0];
~' h\" _2 P& y1 R$ k2 @9 b& u
n=size(w,1); % n记录图中点数* N9 G; @, X1 M. B# e
D=w; % D为距离矩阵
# D5 N) ~7 i3 Y4 Y- P
R=[]; % R为路径矩阵
& |7 v* y4 k: J& O
: b/ x, _: Z6 ]% j/ f\" X2 i
for i=1:n
! s' i8 L+ @3 o# E3 ^ R
for j=1:n
) e8 x. F+ M. q, G/ j- R4 Z
R(i,j)=j; % 为R矩阵赋初值, D% \0 _: W$ z2 G# f3 i7 [
end' N8 o3 ~$ r1 }( i y% m9 @
end4 B. `2 a8 I8 a+ I. c$ X: N+ G/ y
6 |) m, g0 z% r
for k=1:n A- t X$ `$ \& [, U p
for i=1:n1 i& @' y7 K! d) y9 z8 m\" ?
for j=1:n. P0 a* T, n- S k% s D8 U$ b
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
. o( ~/ B4 b2 R\" A
D(i,j)=D(i,k)+D(k,j);
1 H. X' i1 ?! U6 O' j4 v
R(i,j)=k;/ q6 k+ ?. U& H# T$ ^2 L
end
) r7 c: x, a% E
end
; j' q' b$ L) ?/ V
end
( p' P+ l) s3 x5 _\" J
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 的最短路径上的中间顶点。