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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; 2 p3 R$ `! h3 g1 `! O
2,0,inf,3,3,1,inf;
3 p0 t) Z5 r: m; ~
4,inf,0,2,3,1,inf;
4 t\" ^! ?* Z+ W1 S8 I
inf,3,2,0,inf,inf,1;
/ e' }% f# i5 ]
inf,3,3,inf,0,inf,3;
3 M1 n7 v6 T& q, K* {
inf,1,1,inf,inf,0,4;5 n X0 z/ u6 ^5 S. k
inf,inf,inf,1,3,4,0];\" N\" j9 t; K! _
n=size(w,1); % n记录图中点数$ h9 Q9 ? }, D6 A
D=w; % D为距离矩阵
( Z5 h8 _* s7 T) G
R=[]; % R为路径矩阵; ~; J7 G9 ?& U+ J0 N7 P
; e7 p7 f\" x+ g9 P. {9 ~* Q
for i=1:n; y$ Q) G2 a+ a9 Z
for j=1:n# B: M3 C- s! p# A: q0 Q
R(i,j)=j; % 为R矩阵赋初值8 _: D\" [+ \, G, `
end
9 w _, D9 j\" t4 c* P\" E
end6 J3 W. l$ F8 ?1 G+ d) l
+ }- c W6 i/ n2 Y& O4 l$ z, ~) b
for k=1:n : k- R8 \ y' S' Z( v: p5 m
for i=1:n( f, }3 y' v9 }9 n# t
for j=1:n
7 \. k4 J- u. d. c* t1 p# h
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
) r+ B8 Q0 R8 E, k, a# A+ o4 n
D(i,j)=D(i,k)+D(k,j);
7 N2 E) I4 S# e. f\" s7 `' k
R(i,j)=k;
end/ O# @; Z8 ~% m3 `, s4 O
end) P( J* A8 Q! l* \
end! z4 B3 l t7 b o, }2 I# k
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 的最短路径上的中间顶点。