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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; 7 Y% I% O @( i9 \3 V1 s
2,0,inf,3,3,1,inf;
1 E* Q* ]5 M2 @8 _5 O! i. @
4,inf,0,2,3,1,inf; ( y: o' j5 j( `4 S- Y& T5 s. q
inf,3,2,0,inf,inf,1;
5 Z, a: T; t! U8 k0 f: S
inf,3,3,inf,0,inf,3;
1 o\" [3 {; e( V# ~$ ]4 u; ]
inf,1,1,inf,inf,0,4;1 F/ v7 B! r\" K, J& h) r% X
inf,inf,inf,1,3,4,0];
5 G- J; a\" ?. e, U8 O' Q) [
n=size(w,1); % n记录图中点数
3 K& n$ d# R& ?
D=w; % D为距离矩阵
6 h7 ?\" `& H\" ^0 u8 U2 W
R=[]; % R为路径矩阵
8 _& ^2 S0 a3 V
3 e) @: O1 b* y\" ?$ V8 {
for i=1:n
6 d9 S7 B2 p( Q* Z/ F
for j=1:n
7 j* ~7 A; j' P/ ^% H8 K
R(i,j)=j; % 为R矩阵赋初值& f( J% X3 S1 D! W2 P7 }
end
/ E6 J& v# c1 ~/ V# g3 ?5 U
end
% v& e& J7 \8 x# f\" C) w* S
9 N+ f7 u& W1 ~* D9 B+ o
for k=1:n 1 q: {9 e. m) | U3 V, }8 V
for i=1:n f: s. N2 j3 Y7 _
for j=1:n! x* A/ {4 ?% r
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
0 @+ z* P6 O! x8 s' s\" D. v; X. G7 z
D(i,j)=D(i,k)+D(k,j);8 i) _! \; G4 T/ k5 o
R(i,j)=k;
) Z G/ W0 x# d/ v
end5 R+ j% B/ [! q- S1 X) D7 `
end
& z! F$ [$ Q( _. a6 A/ h
end
' r- v1 ~0 q, L
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 的最短路径上的中间顶点。