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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; ) F4 ^/ \! H9 f! Z( B6 z8 t: {
2,0,inf,3,3,1,inf;
% j! h\" e1 T% v5 T; a5 E
4,inf,0,2,3,1,inf; * V# M3 H& D! h& o+ k' C
inf,3,2,0,inf,inf,1; - N7 u9 z6 i0 Y; ]: {) V n
inf,3,3,inf,0,inf,3;
b' Z3 q1 c5 l0 t9 q1 H4 s
inf,1,1,inf,inf,0,4;
5 }) B4 M6 w+ ^! @) x+ V0 v1 j$ S) z3 |
inf,inf,inf,1,3,4,0];
# l1 q: e\" \5 T) n
n=size(w,1); % n记录图中点数) X4 O/ {1 G# \8 ^5 c
D=w; % D为距离矩阵7 o( F$ i/ Q; U+ `/ [& u1 K% r0 _
R=[]; % R为路径矩阵0 s t/ @5 d, s2 l) B) U
+ N( X! D! v7 A
for i=1:n
2 q$ `6 | X# s' g
for j=1:n
$ K+ i1 P7 F2 }4 L- i
R(i,j)=j; % 为R矩阵赋初值! \. [7 E\" X7 A
end
& B: `$ H \. n2 F! _
end
) j ^) w0 _* y/ k. x
$ V# n2 A2 M u% k( S9 B& e5 r
for k=1:n
$ a. Q' E* F7 T5 s
for i=1:n
) E; w2 Q' K' I% n4 A
for j=1:n& j3 ?( K: T\" u: I# k- ^/ A
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
& C- ]# x& \% O\" @
D(i,j)=D(i,k)+D(k,j);. x% [# u2 W6 C/ a) V
R(i,j)=k;; h4 Y- E% L! L( a! ?, j! _
end+ {1 _/ I1 K7 F4 k\" O2 Y, a' ?
end+ j8 i% [' h1 \1 t+ y
end5 E: X( ?) e e' 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 的最短路径上的中间顶点。