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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; * x\" C# A7 z1 z' f' ?
2,0,inf,3,3,1,inf;
8 {) i2 L\" l6 F2 l$ {
4,inf,0,2,3,1,inf;
. M+ O\" Q7 u: ]8 n$ I6 h/ A3 @
inf,3,2,0,inf,inf,1;
! g1 V4 X1 f% t' t
inf,3,3,inf,0,inf,3;; k# l1 X\" }3 Q# [
inf,1,1,inf,inf,0,4;
) f; x) O* c) l, R
inf,inf,inf,1,3,4,0];& ]3 g8 C1 C4 M% e
n=size(w,1); % n记录图中点数
( G5 {: F- M1 d
D=w; % D为距离矩阵7 e& Y# L4 o5 \7 W
R=[]; % R为路径矩阵+ @4 A7 c+ o/ r& F, {3 d! X {3 k
$ j# l9 F1 P1 z2 D4 i! [
for i=1:n
9 X8 d# h2 g2 W) \
for j=1:n6 ]8 o) Z# x+ T
R(i,j)=j; % 为R矩阵赋初值. v3 Y0 k; z, U& P% X8 j% ]
end8 w: I) L# \\" Y1 Z5 _
end \5 C/ H, N8 f% M
* T5 {. [7 C1 }9 q2 t' S
for k=1:n
: j; | t2 k' M8 c; T- a. J
for i=1:n
# H\" {0 P# p3 k
for j=1:n3 Z2 d- r2 C' f3 @+ ~* O
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
$ G/ d+ H7 [& t9 w% G
D(i,j)=D(i,k)+D(k,j);3 A0 l; h' p& b6 _# r9 M
R(i,j)=k;5 S* V+ s8 ~6 _# J7 n3 a
end, s3 m0 j# i( o5 Y
end0 L9 @\" ^7 H0 l: O- X) s) \
end/ ~7 D- l3 C8 \, a: r/ X
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 的最短路径上的中间顶点。