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

[复制链接]

字体大小: 正常放大

2744557306

1188 主题	4 听众	2931 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; ) o# P1 P3 S- O; ?* A
2,0,inf,3,3,1,inf;
% p }: T! U) {. O7 P! x: x) R9 y
4,inf,0,2,3,1,inf;
6 Q( Y4 o4 B3 w, J: |
inf,3,2,0,inf,inf,1; 2 l4 K1 E( Q! X9 i5 S
inf,3,3,inf,0,inf,3;
# Q1 `& V5 G! X4 u) D) H
inf,1,1,inf,inf,0,4;3 {- o' [! H3 k9 c& X+ Z7 @# N- s
inf,inf,inf,1,3,4,0];
) N, R0 p- k6 g% m& @% c6 L' K
n=size(w,1); % n记录图中点数
0 D+ o5 h1 v0 k; C% I+ J! v# c
D=w; % D为距离矩阵
+ V1 ~3 p+ q; e! j% E4 ^
R=[]; % R为路径矩阵\" ?7 \6 E w2 ~% p9 e w
8 u, E& |3 o: |6 s0 x
for i=1:n: a# [) y. E' T! ~. x' C- y1 z& S
for j=1:n Y' d, L: Q, x( ^2 G+ W7 Y
R(i,j)=j; % 为R矩阵赋初值. C( {0 B5 Z4 l J9 C' @* f
end# c2 d7 R* ^5 b- ?
end
2 O# s( V) U( J; W
5 d9 q: s, M$ L+ z\" L4 }
for k=1:n
, ]! ]1 @6 g# K# f\" D/ b5 u
for i=1:n/ Y, h' K0 A7 @9 x! I7 Z
for j=1:n: f0 M) J/ L* @# j0 R+ }9 U
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
4 G3 i3 B$ n5 S9 W% T; s% a7 W
D(i,j)=D(i,k)+D(k,j);* k2 s$ i' Q0 C! T8 D& u3 ]9 s* H- M( n
R(i,j)=k;
- ^8 l: |& C% K0 R1 x
end
, ?% v# w' H\" t9 R( \
end3 ~- Q/ e0 }) t, v\" x; `' Z
end8 I1 F. {! x$ {5 d: k% {
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 的最短路径上的中间顶点。