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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf; ; v) W; v4 `0 B: i2 k0 Z+ k% y: v
2,0,inf,3,3,1,inf;+ z) h$ N8 n5 L' `9 U0 o2 Y
4,inf,0,2,3,1,inf; \" ~2 E8 q. i/ q6 l4 Y z+ ~
inf,3,2,0,inf,inf,1;
. V1 V5 V- D/ @5 K( _( ?
inf,3,3,inf,0,inf,3;
: U8 k2 q. D* j, [
inf,1,1,inf,inf,0,4;
) c7 B6 d7 G. H* m: y) C/ w
inf,inf,inf,1,3,4,0];' o9 i/ K; |9 K0 u& e4 }2 N9 n. W
n=size(w,1); % n记录图中点数& u: `2 P- I; d
D=w; % D为距离矩阵
* i0 M' g6 j\" d+ |/ D0 ~- G
R=[]; % R为路径矩阵
1 Z! E& B# _* K: e
: l4 z7 ^. Z: Z
for i=1:n) W/ ~: g3 ?8 J5 t' v$ ~
for j=1:n
2 q/ x5 t8 `2 _ B% C
R(i,j)=j; % 为R矩阵赋初值
( r\" g6 \. z) D2 C\" V
end
- G/ S; i% ?8 X& H
end
% [) b, h' r9 b' c& d9 r
, m* U ?' D6 I
for k=1:n \" b- J- d/ H0 q8 M) b7 q' @5 w
for i=1:n1 W/ `\" ]7 W' {, t. z
for j=1:n3 w3 d S t7 k
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件 8 P& F, W$ A' [, D! Z7 `( G% D8 f
D(i,j)=D(i,k)+D(k,j);: [4 p3 g\" [& q- |: T6 |\" H
R(i,j)=k;
\" E) r b1 t\" A6 {0 U; o
end3 @& L! {( C! v
end\" v+ y v9 Y0 X8 l4 c
end( k! u f/ D# I6 h* y5 m
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 的最短路径上的中间顶点。