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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; 5 e. k1 J) F) Y: {
2,0,inf,3,3,1,inf;
8 _0 t3 V) {3 b( C5 [- a' v2 a% s6 |) d
4,inf,0,2,3,1,inf;
' A1 o0 N& ?1 B8 w* _' r4 c
inf,3,2,0,inf,inf,1;
/ E7 v/ Z) J6 ~- @1 r: |
inf,3,3,inf,0,inf,3;
0 P3 l; H/ N* u5 E, q* n: L0 b
inf,1,1,inf,inf,0,4;
# G d2 R0 n8 Y, n3 P9 _
inf,inf,inf,1,3,4,0];3 q# f8 r5 j( f
n=size(w,1); % n记录图中点数8 G% l. S- }7 v( S7 w8 Y
D=w; % D为距离矩阵# @5 r- C5 j: w3 b% X# c& ]6 O+ N$ n4 h
R=[]; % R为路径矩阵
; a) w# t7 C( y
& V Y8 [- R+ \\" d% x
for i=1:n
F0 s0 s- q1 g+ y/ d0 `1 V: p7 C
for j=1:n
1 I* P\" ]% O6 z( Z$ {$ J4 Q
R(i,j)=j; % 为R矩阵赋初值
3 r8 X/ w: ^, T4 H* y- z
end6 C2 o! L4 i! F& b, A
end
- Y, L& d* j; G9 ~/ X1 G0 O9 u `
8 E0 h/ x7 O7 y
for k=1:n
) G7 V7 r# i* I0 m1 [; d% S7 H
for i=1:n
' r6 {7 V6 P6 d3 R$ s6 ?9 s
for j=1:n
, [1 P/ F/ L9 \$ w. O# K, [
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 & R( u2 ^1 ^$ c7 u) e$ W8 B
D(i,j)=D(i,k)+D(k,j);$ P* e0 ^+ e1 B) E
R(i,j)=k;4 Q\" P2 a6 T- s+ O. ?+ S/ s. y
end
, p1 T: T# \: R, G/ w2 Q
end* T2 Q+ G# u& f3 t7 Y$ a& r
end
! u2 a, m! x! H' g) B+ L
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 的最短路径上的中间顶点。