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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; & X+ z/ D; A6 S
2,0,inf,3,3,1,inf;9 [8 @5 v( `\" T$ f
4,inf,0,2,3,1,inf; 9 G( t; M. ]; D& z% n& V9 O6 d
inf,3,2,0,inf,inf,1; 7 y- j' C$ W, z$ p: e, O
inf,3,3,inf,0,inf,3;
; C& A6 _+ Z; w+ ~& @9 P
inf,1,1,inf,inf,0,4;
/ o- S2 o0 I1 R: e# h4 v
inf,inf,inf,1,3,4,0];
) f' W7 T7 Z/ L
n=size(w,1); % n记录图中点数
5 b: q' w1 `2 G$ i9 J. E
D=w; % D为距离矩阵
3 e$ H1 T6 a) |7 @1 I
R=[]; % R为路径矩阵
8 a2 ?+ F6 C( e2 n' A( D L
: ?+ A0 n# ?/ W; B& a% o# R2 J* X7 c+ C
for i=1:n
( \& n! e5 }0 O
for j=1:n- m' y8 A: o) `5 K' w' m
R(i,j)=j; % 为R矩阵赋初值, r6 ^, T6 ?& w1 g4 s6 i4 b$ p
end: `* x1 ]& A* B1 E
end% q# z0 W* ?. S+ f9 q( ~. ~& N% t; G
5 M' w. Q/ G- ?6 e c
for k=1:n 0 L! w5 _0 n8 y+ U* T Z
for i=1:n8 X% Y' p$ e& L: O& _: g
for j=1:n
/ v; S& K\" d: C8 V& M
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 U' R* G: R\" ^% i/ s' Z6 c
D(i,j)=D(i,k)+D(k,j);
0 C, f$ V& |' Y f9 B
R(i,j)=k;$ P+ e# v\" U& m/ K
end
3 z: N' J! r. a2 ^6 Q; J
end
: J6 {/ Z( P+ B, U$ T( q
end
8 L0 p; s! I1 }9 \+ X8 J
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 的最短路径上的中间顶点。