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

[复制链接]

字体大小: 正常放大

2744557306

1186 主题	4 听众	2922 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; ' c5 d o$ w6 Z/ p
2,0,inf,3,3,1,inf;
% |+ U y3 S- H6 }6 w4 r l
4,inf,0,2,3,1,inf;
( V# g. T* ]+ _ @. b% y4 c2 W
inf,3,2,0,inf,inf,1; 6 l9 ?$ \# o2 ?\" N( W& O' F
inf,3,3,inf,0,inf,3;4 I\" u9 D: I* d- K: q+ N
inf,1,1,inf,inf,0,4;9 v6 u4 \) U2 w* Y1 C$ m; ~. c4 d
inf,inf,inf,1,3,4,0];1 U4 K% p) \# G/ W0 y1 l- w( }
n=size(w,1); % n记录图中点数$ C6 C( @\" S0 w/ L) ^
D=w; % D为距离矩阵+ n1 L4 x0 i/ g$ N* R* m
R=[]; % R为路径矩阵1 C/ Q( y1 _% k J4 k2 ?6 Q\" t8 q
\" Z7 l8 Z7 o7 y3 v- Q) l
for i=1:n9 f. `2 e) I3 V2 \6 j$ m; l- u
for j=1:n
# E# `+ f7 J; D\" O8 I+ C, l7 g1 h
R(i,j)=j; % 为R矩阵赋初值
8 h* C\" ?\" ]( x- ]
end
5 [1 x( M7 M; e4 g! [8 f
end
' Y% \: `5 ^2 \( _; ~
+ S9 ^; \4 L+ B$ j. W; ~- j
for k=1:n * Y$ P! V5 w1 C- N8 B1 h7 c/ q
for i=1:n
% T. A2 j& N3 {; o5 E C1 T
for j=1:n s2 R# f0 o$ G5 M: O% F
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
D(i,j)=D(i,k)+D(k,j);! W: ?' ]* d- o3 K
R(i,j)=k;5 a$ o/ p& q0 U/ c9 n8 q
end+ A: K- ~' e8 M' M# [% R1 n* e1 `
end! {$ r. K: ^\" l5 t+ ^
end. S# m+ K3 w( ?2 [4 O) u
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 的最短路径上的中间顶点。