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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
* H: T& M. u2 @. A2 X/ T
2,0,inf,3,3,1,inf;
3 z7 k5 V% l& O9 X- o
4,inf,0,2,3,1,inf; ! L- c) m( q H% m3 z4 t* F: j8 s
inf,3,2,0,inf,inf,1;
+ F, Z) B$ ~\" }$ d- p
inf,3,3,inf,0,inf,3;! `% s ^/ E W. Z
inf,1,1,inf,inf,0,4;! a1 x& ^' N& n8 H. D
inf,inf,inf,1,3,4,0];9 K7 D7 z2 ` Q: H, h. t
n=size(w,1); % n记录图中点数- @, i2 W. a+ v0 j! k; f' y$ Y- C$ B
D=w; % D为距离矩阵) l6 T: p. L9 {! J& W( W, u O
R=[]; % R为路径矩阵- F) U1 h- O9 H V& k5 g
2 J# y- }; F: ]+ s* O( i7 M- m1 O/ E
for i=1:n K; E6 f: W( f$ S3 }& ]7 s
for j=1:n* L2 I, n; Q( ?) D: P: Q3 t5 e
R(i,j)=j; % 为R矩阵赋初值
+ y\" j L7 H+ v; T\" J
end8 i- |. G v8 v0 e. i
end
5 d/ N; W3 H! j& y
) x% j' R* Z6 v- q0 v; j6 N$ ]
for k=1:n
1 e& a( C; X) a4 M8 ^6 a6 W
for i=1:n
$ R/ }& n' B) i6 R7 n1 L- N
for j=1:n; F C0 W7 m: O\" J
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 8 @* J\" @\" j, ?4 l. G6 [
D(i,j)=D(i,k)+D(k,j);
9 M& B9 S0 k! p3 K
R(i,j)=k;
9 G1 ^8 V- x( K0 w! y2 ~
end, R& B, { @; ^8 Y. i( c
end* C7 s; |( h0 `9 m1 T( _
end0 [ E+ S p2 f% b8 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 的最短路径上的中间顶点。