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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
7 z$ ?' `$ L% h) y% e# C
2,0,inf,3,3,1,inf;( T& [* Z6 _( S: u
4,inf,0,2,3,1,inf;
) t0 _. @3 E. n% G- T3 W* u7 D6 W# |
inf,3,2,0,inf,inf,1; ( z8 e- j; K9 C' N! I' L
inf,3,3,inf,0,inf,3;/ t4 }; g: I K
inf,1,1,inf,inf,0,4;
6 Z. d8 k! w* I- T' \: n1 q1 k
inf,inf,inf,1,3,4,0];6 w5 L7 h) g5 W% f- n8 M
n=size(w,1); % n记录图中点数
5 G+ n7 D: V# U0 b
D=w; % D为距离矩阵6 [\" m& \1 c; b% L: I
R=[]; % R为路径矩阵
6 a& W% x; Z' N' [6 W
1 B H9 `# Q$ R' x' b: L
for i=1:n
4 V$ G: [! Y, e. R$ z
for j=1:n
6 T; n* ?/ Y1 ~! z* `& Z; W3 f
R(i,j)=j; % 为R矩阵赋初值9 Y/ T& M+ ] l! q
end5 g: ]: x* p/ y8 B
end* s D7 I, x* O6 V
% g l1 x3 a) B2 m$ c0 D
for k=1:n
' p- @: S; C# ~9 _: ] d+ `$ z
for i=1:n\" M) P\" @6 a0 H9 D+ I! F2 h( \( I8 f
for j=1:n$ \3 E- S, |5 Y5 o1 \
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 1 y! z' W5 T9 y, t$ e; K4 d
D(i,j)=D(i,k)+D(k,j);) Y) E0 [0 p2 j6 \) Z
R(i,j)=k;5 f7 T/ @' \6 R6 V. f3 D% ~
end, Z* g; l; D' r: [3 N
end
, u, x; c2 }1 t# J
end( [& G; i( D& B V; |
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 的最短路径上的中间顶点。