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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
# ^6 {+ x4 t5 ?/ o
2,0,inf,3,3,1,inf;& x: W7 x3 j7 J) x! ^) _; ~4 c
4,inf,0,2,3,1,inf; 2 b( `\" U& c% b8 X
inf,3,2,0,inf,inf,1;
% `\" B1 |' @\" Y* C6 b
inf,3,3,inf,0,inf,3;
% S- z, s8 S. C* m- X2 d
inf,1,1,inf,inf,0,4;- O) s: Y( ?4 D, C; t
inf,inf,inf,1,3,4,0];; x3 o, Q: m: `* A: s
n=size(w,1); % n记录图中点数
& O$ s* Q+ g+ N8 R1 S: {6 V1 K
D=w; % D为距离矩阵
! x4 N q6 R3 [- {\" X
R=[]; % R为路径矩阵
( G/ E7 j0 K9 t2 z( s- Q Z1 j3 U
2 D. U; T% ~# g1 }$ i
for i=1:n
+ n* \) F6 \4 @1 e5 P4 B
for j=1:n% C8 a5 |& l2 I0 U8 {1 f
R(i,j)=j; % 为R矩阵赋初值6 b& y. ~4 C3 ~* ~
end8 t* U0 g7 u1 [\" l$ U- w
end
/ L- r& X$ ?\" O2 K' O1 ]
! ~# S; @' G7 C- p
for k=1:n + g: B/ \\" ?5 N0 k8 q3 t- ^
for i=1:n3 A* D4 {9 J! o R8 K
for j=1:n
' j! L) H0 Y# X# v. w
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
( R& ?% ^$ P, u
D(i,j)=D(i,k)+D(k,j);& R. n7 O' b' k& D
R(i,j)=k;
& @4 x L+ U. @$ S( v9 a7 h
end/ ~: o: G k. z3 `; O3 w
end9 S7 s% W$ `\" D' ]7 h! O6 j
end4 b+ w! e! N; v+ p% L l, 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 的最短路径上的中间顶点。