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

[复制链接]

字体大小: 正常放大

2744557306

1171 主题	4 听众	2781 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; 7 f; z; ]/ Y% A' c
2,0,inf,3,3,1,inf;- \% m# H; v0 Q& g. R; g4 [, @
4,inf,0,2,3,1,inf; ! e! M- H5 {+ X9 {
inf,3,2,0,inf,inf,1;
0 k! V. Y; E2 A, U* p( @3 ~2 u
inf,3,3,inf,0,inf,3;4 s' k$ D3 e; _, Y9 D
inf,1,1,inf,inf,0,4;
^4 p\" ^3 E2 Z$ F! \1 p
inf,inf,inf,1,3,4,0];/ s+ `1 W$ m. `% c7 c
n=size(w,1); % n记录图中点数6 w/ m+ f, q5 U7 Y# b _+ ?
D=w; % D为距离矩阵
- @8 P8 T2 S$ P$ x4 V* m4 e
R=[]; % R为路径矩阵
\" v; V2 n% ^# U# U
, J7 G) O* K4 F1 L3 u& V/ x1 G
for i=1:n
- p1 s+ y. G5 @! Y7 F
for j=1:n3 w& P) q1 P1 ~/ X5 @$ Z
R(i,j)=j; % 为R矩阵赋初值
1 R- \2 L* ?9 C; ?\" D# I: j
end) i\" K# e I6 \+ Q
end
4 C0 h: Y: o+ {8 V
4 N3 d/ p }5 g
for k=1:n
7 z; D' W& e: }1 k/ t6 E
for i=1:n
+ p# S6 y! }- S\" X9 a
for j=1:n# r1 a' t8 s) \
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
, B( D. j1 K0 v
D(i,j)=D(i,k)+D(k,j);
+ ?# W' X( N# \6 c4 |+ y
R(i,j)=k;' f! k0 y/ ^9 H! I5 |& n
end! A$ [$ ?' M! K2 D7 S
end
- H9 I( s\" z2 M+ B
end
- F2 ^3 N! U1 _! i
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 的最短路径上的中间顶点。