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

[复制链接]

字体大小: 正常放大

2744557306

1198 主题	4 听众	2976 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
+ z6 Q4 v* u\" }, t9 H
2,0,inf,3,3,1,inf;
5 r% n6 f- U6 z& h
4,inf,0,2,3,1,inf;
7 m- f7 j/ Q% u: G
inf,3,2,0,inf,inf,1;
! `- E5 L _9 G5 i
inf,3,3,inf,0,inf,3;\" O) i7 m# v9 I
inf,1,1,inf,inf,0,4;
2 x3 w) |1 d& u y$ Z! o
inf,inf,inf,1,3,4,0];
; J/ o7 \, q0 i
n=size(w,1); % n记录图中点数
/ D6 ^9 Y* I! ~/ _
D=w; % D为距离矩阵
: u5 f) a7 A: ?0 T8 `: Y6 N+ G* V3 W( R
R=[]; % R为路径矩阵- }3 p9 L' t: j2 a0 t5 D
% I3 I3 G) F$ [$ c8 ]& n$ f
for i=1:n
- S4 v$ {9 s L+ [ d- O
for j=1:n\" l8 v: C; ^: ]) b P% b$ _( ?8 ^1 r
R(i,j)=j; % 为R矩阵赋初值
( V4 f+ r6 \; u. h& \
end
% m* {; w+ W5 ^# Q
end7 x/ F' L+ [: S& T
1 n9 }0 d; @* y
for k=1:n 7 ?, ]7 c3 ?. _) G+ v* ?
for i=1:n! Y- }\" B/ B. X! H$ J
for j=1:n
% @* _- o* c1 c- i6 H n\" ^, y! o
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 0 V4 D& b/ l' C V: Z\" ^/ C
D(i,j)=D(i,k)+D(k,j);$ Z; {3 n. ]: @: y\" R* E
R(i,j)=k;
) {/ X' j# F4 C9 u% Q\" b$ S
end! H, X- j8 K3 y4 e3 R V* ^; ?; a
end8 i% V/ ]3 s0 T N
end
+ `3 x: @' H* a
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 的最短路径上的中间顶点。