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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; * m! G/ ~& ~+ F, @# ^: u; Q2 H( A+ J
2,0,inf,3,3,1,inf;# z5 m4 B$ l: z: z9 \# t9 w3 O
4,inf,0,2,3,1,inf;
- W) l: i' {' q3 Q0 ~* ?. _, b
inf,3,2,0,inf,inf,1; % A C% C- o& Q u1 \- ^5 k
inf,3,3,inf,0,inf,3;- J: {) A7 T4 F8 V+ ^3 e0 f
inf,1,1,inf,inf,0,4;
- m* P. R% \, m0 G. |1 |
inf,inf,inf,1,3,4,0];# }: [+ d; n; v9 W
n=size(w,1); % n记录图中点数
: }2 ?! g( z, Z+ U
D=w; % D为距离矩阵
$ {/ F6 X* n6 a9 T# K, F+ M( `- P
R=[]; % R为路径矩阵. h; h h G9 W: h* I/ S$ O$ O# h p2 z
0 t1 Z! [' ^( u* k: N
for i=1:n
% a& x. P/ U9 u0 @: x) g\" a+ b
for j=1:n6 m1 e; G! Y3 g/ h
R(i,j)=j; % 为R矩阵赋初值) A1 W* T, H( r4 N
end
, ^; O# f0 T7 ?
end- u7 R) Q. q( q/ c! k0 x/ I4 R
% b+ f3 o, R2 w! D
for k=1:n
% I9 `5 o% x; _9 n1 C; s6 n4 k
for i=1:n
, a4 f( y, N) r' t7 P: N% c
for j=1:n% g! \7 N7 u& n! R
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 ) A6 D1 m3 ?- w6 d. N- ^
D(i,j)=D(i,k)+D(k,j);- P6 x/ H! u0 l9 N* w7 m
R(i,j)=k;
O$ }\" n ?7 W. m
end
% t5 J9 N3 Y$ P. F
end
! D) |1 u9 b5 b W# T5 [
end
$ [! [( q$ c H4 |
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 的最短路径上的中间顶点。