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

[复制链接]

字体大小: 正常放大

2744557306

1171 主题	4 听众	2780 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
1 e; R! r, q4 ~\" z7 [' d7 P$ X
2,0,inf,3,3,1,inf;
! l- L; \. ^- s& m$ Q$ F5 v\" }9 q
4,inf,0,2,3,1,inf;
& H3 T$ r8 D9 h) h2 m8 w
inf,3,2,0,inf,inf,1; / k; g! A W. @7 v2 M
inf,3,3,inf,0,inf,3;
* d! ]( {. s/ o3 L2 z
inf,1,1,inf,inf,0,4;
\" t; ] z' a( c2 ?3 N( i- }
inf,inf,inf,1,3,4,0]; }\" O7 `: j7 R: Q7 Y( K6 d
n=size(w,1); % n记录图中点数
% c/ M. k3 R n% T1 w4 s7 m; B5 E; d
D=w; % D为距离矩阵
: V5 p: e; ^& P- e4 c l2 O! K5 `& I
R=[]; % R为路径矩阵- V# l( F$ T- d4 I0 t2 A
5 B- {: |2 W& X) U- T! d
for i=1:n) R. n6 z# C+ \$ ?! Y) h; N- T9 ^% }
for j=1:n
+ n- M# O( G% t6 h: c0 `+ I
R(i,j)=j; % 为R矩阵赋初值0 C% }% s1 M8 r( ~- l) o: o) J! a
end! y- x; K- m* Y1 Q) v7 N1 G$ E
end
) {( ~+ [* M\" [7 o0 @\" f7 @\" n
\" l* Z9 E& M' r
for k=1:n
; {4 Y X& y+ H: d
for i=1:n1 m, ?1 x) D* C P! d* J/ g ^
for j=1:n% J9 }+ \: p9 _9 [
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
& ~9 r( s- \- L: n- `8 ?/ v
D(i,j)=D(i,k)+D(k,j);0 Y) t+ ]& m5 c9 l' G8 A
R(i,j)=k;
* N# _\" ?% c4 E( u- m4 m l5 G
end
- B& s' W9 }' ? l$ t R$ ^
end
`& u2 M; Z\" A% _5 B
end, I* c0 X9 p4 Y; e% \% w8 X
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 的最短路径上的中间顶点。