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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
; Q2 M8 A5 x. W2 C, U
2,0,inf,3,3,1,inf;2 A C& _4 U, Z
4,inf,0,2,3,1,inf;
! m; a: T6 b' m) u: w1 C' p; x
inf,3,2,0,inf,inf,1;
. j/ v\" I0 b* I: j
inf,3,3,inf,0,inf,3;
# K) @3 [( \7 e1 R* h
inf,1,1,inf,inf,0,4;8 I; p R1 k' T) [
inf,inf,inf,1,3,4,0];
* W! T& f7 i+ k/ l3 h
n=size(w,1); % n记录图中点数
5 G8 k8 o- E- b, i
D=w; % D为距离矩阵& E8 ~. j; _: W. [% M0 W- M
R=[]; % R为路径矩阵
! @4 e; ~( e* I8 w\" }
6 p( Z\" z* U& C
for i=1:n8 n2 Y _* Q$ s
for j=1:n6 l$ d3 @/ i( Y3 e\" G6 v! q, }( V: h
R(i,j)=j; % 为R矩阵赋初值
* |# g- }# a! p: b6 W0 C/ }. P! h/ F2 n
end9 G6 C& A& y$ E g+ y- y
end
: v; p& `$ y H% L% g4 c
' I' K* H. i3 e9 R! P0 V- K
for k=1:n
+ r/ n' L/ n R0 m& Q. n4 T. i4 S
for i=1:n! y* C* N- L) Z6 \& _+ M
for j=1:n
( ?4 Q8 N8 h( d1 h
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
, T, w' |+ m j4 Q* I: [4 m e
D(i,j)=D(i,k)+D(k,j);
+ E( {+ z8 U/ D- }) p0 ?8 B1 H
R(i,j)=k;6 n+ x. w! P \, {; {3 N
end
: S) G+ Y( L5 s' ~0 w
end3 ^8 ~& F# T! ~# u' v, s
end
3 ~- |0 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 的最短路径上的中间顶点。