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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
+ a. I5 q* _$ x/ Q9 G% a
2,0,inf,3,3,1,inf;
5 L- p4 f/ T2 w* ^3 j
4,inf,0,2,3,1,inf;
\" t' R) z! {& g
inf,3,2,0,inf,inf,1;
' B) C @# E. M4 ?1 Y4 l8 T
inf,3,3,inf,0,inf,3;
4 K5 w# i4 q V
inf,1,1,inf,inf,0,4;
' [( T) G; @6 Q% I, p9 @$ |) N5 y$ Y
inf,inf,inf,1,3,4,0];
$ E+ d; B! P* |7 I( X
n=size(w,1); % n记录图中点数
, @0 P3 s4 B- q/ T/ D+ o$ [; ]
D=w; % D为距离矩阵
) G% J) z& \9 J7 f
R=[]; % R为路径矩阵
: \' z% v z. c1 R1 i+ c6 z
for i=1:n1 m/ D/ {0 w\" a1 {
for j=1:n! V+ _ X% F1 f7 \\" Y
R(i,j)=j; % 为R矩阵赋初值. c& e' {) M; n# {# B( W\" |5 p\" w' J
end\" u) G1 Z/ e5 G/ Z\" K9 n
end
# a5 x7 `& G$ H8 e
* H1 A6 x1 D7 f
for k=1:n
/ h- z2 L) C$ w) p\" R2 x
for i=1:n
p0 t1 R7 b E5 q- p
for j=1:n
# ~6 l' c3 u o5 ]6 k* m8 m1 L% D
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
5 s3 G1 k0 k) k
D(i,j)=D(i,k)+D(k,j);
' x' X4 J\" r- x6 h\" {' n! [( v
R(i,j)=k;
4 B/ }; L+ z% e7 F- ?4 S0 Q
end: D% P' g! T3 V( o! @3 |- p5 V2 g+ ?
end0 u1 c% I- K( ?
end- N/ |1 b\" h. l* f! k\" 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 的最短路径上的中间顶点。