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

[复制链接]

字体大小: 正常放大

2744557306

1192 主题	4 听众	2946 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
1 F7 _( C0 z7 f
2,0,inf,3,3,1,inf;: ~! q( A2 \$ O
4,inf,0,2,3,1,inf; ~! b. o- ?' A
inf,3,2,0,inf,inf,1; 5 @* u, @8 M* p' p+ T# f; B
inf,3,3,inf,0,inf,3;
: S8 ]: V* }$ o( l* l8 v
inf,1,1,inf,inf,0,4;6 M; E M( W2 L1 i- u
inf,inf,inf,1,3,4,0];5 S! n7 i% v! V/ d+ B p/ Z
n=size(w,1); % n记录图中点数8 q( z7 h( j- {2 O9 h4 [1 A
D=w; % D为距离矩阵0 ^: l3 q$ U9 X
R=[]; % R为路径矩阵
* }( A ~4 X3 \! q( y0 g0 `
0 R4 [& \ M1 d% Z
for i=1:n6 N1 D5 e: Q5 O0 O- `
for j=1:n
$ x# I. T$ X2 a, L\" a
R(i,j)=j; % 为R矩阵赋初值
4 b/ x2 B9 ?$ G& |; ~
end: C* Z _& v) b9 s
end# b5 P/ S4 E+ Z4 z1 ]) o
- P3 m) b8 R$ Z% O3 D
for k=1:n 4 y$ R3 {& i5 i
for i=1:n' A$ _8 ~# b1 @8 c$ w/ j& W# O\" n
for j=1:n4 \2 `2 U4 O: D
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 ' Y1 Y( U0 a3 E% k
D(i,j)=D(i,k)+D(k,j);
\" C2 ^' b: B/ k% _4 e
R(i,j)=k;0 b$ ? L( R( R\" z! l6 I* B7 ?% i
end! C1 u, e6 c7 S* |; w2 c! w
end2 X9 |! m3 x% `\" }* p- E
end) f. n# B, F$ A
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 的最短路径上的中间顶点。