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

[复制链接]

字体大小: 正常放大

2744557306

1188 主题	4 听众	2931 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; \" i5 d: [% ?/ Y/ o% @; Q6 v
2,0,inf,3,3,1,inf;* z\" j4 v9 I$ a\" q
4,inf,0,2,3,1,inf; 1 y: a- e% |5 B7 C: M
inf,3,2,0,inf,inf,1; $ N$ Z* F7 G. C7 {. i- A% z7 O4 A
inf,3,3,inf,0,inf,3;* ~\" S9 z% U: B
inf,1,1,inf,inf,0,4;
) ~: L* o, {& ^; R
inf,inf,inf,1,3,4,0];
: B5 G7 l ?; V7 j6 Z
n=size(w,1); % n记录图中点数 F, ^# ~+ u/ o& m: j( p
D=w; % D为距离矩阵) y' h) m: M- Y\" L) C; _+ N# m
R=[]; % R为路径矩阵) G; |+ @& H# h' o2 I4 A, y$ i! n9 e
- T2 y8 Y, N\" }! a0 t, o
for i=1:n
\" m1 w: |; H8 ~4 _
for j=1:n
4 ~/ V% y! S/ ?9 H' d) ]
R(i,j)=j; % 为R矩阵赋初值* q( f0 q7 _* S9 Y6 B+ ^; h+ p
end
2 J\" f! ` a/ ~. T9 v6 T$ y& }- k
end5 a\" N9 K2 I\" p' N) h2 B: }- S% v5 ]' t
, z# \3 D* p* O\" H0 F0 ~
for k=1:n 8 M( n0 d3 b1 }% d
for i=1:n( o\" G( ^0 f# I\" g% l3 ^
for j=1:n
8 A/ w+ L2 j- i% i6 K7 a
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
% G3 O0 K; W. M$ s8 D) s
D(i,j)=D(i,k)+D(k,j);: z/ P; g; L- B\" B
R(i,j)=k;6 C. w( {9 O' C8 V, r( T
end! p7 i7 l; T: `
end1 \- U7 U4 g; T- [8 C
end7 m' O. `9 h3 c/ R8 Z* }% {
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 的最短路径上的中间顶点。