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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; 0 Z3 N- n9 _. L9 e6 A' Z' k
2,0,inf,3,3,1,inf;
7 O; @. B6 V\" `
4,inf,0,2,3,1,inf;
8 ?0 U( W& }) ]
inf,3,2,0,inf,inf,1;
, F. [, v5 e: n9 D6 X
inf,3,3,inf,0,inf,3;& C; V/ ^( m$ z% O1 r
inf,1,1,inf,inf,0,4;
7 p7 H. Q' b, V, O' n% }( S/ t
inf,inf,inf,1,3,4,0];- n& b/ I\" O6 H$ s
n=size(w,1); % n记录图中点数' \1 B* ^3 q( y3 h8 j ^0 T+ Z
D=w; % D为距离矩阵
; Y+ Q* `4 U\" e8 y( V* M* d, g
R=[]; % R为路径矩阵3 x( f0 O: ~( s( r$ u$ S
}\" Y1 d+ r5 B% G
for i=1:n
# Y9 V. M\" {5 A: j. M# q
for j=1:n* c\" F) P9 l) C5 J# W
R(i,j)=j; % 为R矩阵赋初值
3 _4 v& t4 p$ X) t8 X% e2 J1 G
end- H! d; `( {* s1 D7 Y/ `( ]7 O X ]1 J
end; o3 S+ p1 f* M, ]% r
# r! T) E. Q6 Q/ f8 w
for k=1:n
5 o$ g$ m+ i! X
for i=1:n4 h0 l3 `, O* B
for j=1:n
/ ~. k- {4 o% @) T/ r) `
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
' J7 A: V6 y6 }
D(i,j)=D(i,k)+D(k,j);- N0 p$ P8 X! H) Y
R(i,j)=k;2 L% O: R& Q* c4 s
end
% K/ p+ b$ b8 l
end
8 L+ Z c8 z' A
end- ^1 t9 L' F- X3 y4 f
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 的最短路径上的中间顶点。