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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
3 q- G' q; N8 P# Z
2,0,inf,3,3,1,inf;
: O! a t( P6 u% m {6 k' P
4,inf,0,2,3,1,inf; 7 M4 _) K7 f3 X' o S8 G; h
inf,3,2,0,inf,inf,1; 3 L# s9 s3 M# w. A
inf,3,3,inf,0,inf,3;3 }8 L1 y- X% J1 F* i0 T, U$ ~6 n( }
inf,1,1,inf,inf,0,4;6 T2 g$ |. b( i) O1 u$ j
inf,inf,inf,1,3,4,0];# X& E; |3 c5 p' m
n=size(w,1); % n记录图中点数2 i; r( Y, |( P: @: |
D=w; % D为距离矩阵' ~/ K8 n* q9 C. X
R=[]; % R为路径矩阵
- I4 @* I7 z% i
3 v3 F( ?; X, m5 s( K3 {
for i=1:n8 Z) t( Y, F8 e\" [. |3 X6 X
for j=1:n
* T( L! v* a\" q' l* a' `8 q- s6 e
R(i,j)=j; % 为R矩阵赋初值% y! ?' b0 A% R5 J0 [, i+ }# |
end
& x. K* p! Q V; J( c* U/ t
end
% A( S) V, Q6 [. ~. G; Q; ?
9 E& d, r: ~5 `
for k=1:n
, r8 Z ~% L) A/ h- u
for i=1:n
9 c5 ^: {( @ I' h* E
for j=1:n
5 u* S5 ~$ T4 ?4 P3 O( U1 \
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 $ \. d, f4 n4 N/ L+ ~$ p2 g
D(i,j)=D(i,k)+D(k,j);
2 m6 P' O; R2 b# m! p
R(i,j)=k;5 G8 |0 J. ^& O
end0 V- o' N5 E* H, @ ~
end
8 m3 \8 a3 p0 X$ `# e
end, a) A% [+ @$ j7 y\" T% E
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 的最短路径上的中间顶点。