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

[复制链接]

字体大小: 正常放大

2744557306

1189 主题	4 听众	2934 积分

该用户从未签到

电梯直达

1^#

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

|招呼Ta 关注Ta

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

w=[0,2,4,inf,inf,inf,inf;
; ^% p: k+ T. w- z& D* J( x
2,0,inf,3,3,1,inf;
4 O0 ]' U/ `! {9 k! x
4,inf,0,2,3,1,inf;
' \$ b$ ?/ J- {9 X$ m. q2 a
inf,3,2,0,inf,inf,1;
8 B. n3 o- R+ r7 }& w
inf,3,3,inf,0,inf,3;
+ A N) T( Y- M
inf,1,1,inf,inf,0,4;1 H% y* B& a4 @! w9 _4 z
inf,inf,inf,1,3,4,0];
0 r( I8 l- ~! J: I+ ?
n=size(w,1); % n记录图中点数6 `8 N5 W/ b3 z! c
D=w; % D为距离矩阵; _- K/ | {- [9 [
R=[]; % R为路径矩阵! A, z- z# M2 p8 |0 k I
/ l7 ?7 r5 T2 J7 Z+ Z2 ^
for i=1:n. ^' F1 D' }: O, E& o8 i) ^
for j=1:n
1 i/ O& Y4 f4 ]& @5 V
R(i,j)=j; % 为R矩阵赋初值\" w+ s s. r% y; S Y* G- p
end\" O( ?# t/ l- `, k4 @# K- z2 u
end
% w/ {\" Z$ ~( n1 O5 Q6 o1 c
2 g5 x' q; w9 Q: T, E( o; i( T; A
for k=1:n
, Y% ~3 F3 H* d4 q, d3 k; S* G+ h- H
for i=1:n; _ Y- d! o _3 T
for j=1:n
. q7 D) n7 H% f
if D(i,k)+D(k,j)<D(i,j) % 判断是否满足插入条件
( Q6 B6 p& a$ W1 T& F
D(i,j)=D(i,k)+D(k,j);
4 E# J9 E% a) ], K
R(i,j)=k;
+ U0 D9 l\" D1 ]7 Z6 l
end
$ C0 W3 Q' _! ~* ~& ~\" s
end2 p# I/ ^2 @6 j# h
end
/ ]/ [! B$ z( y* |, j( `' J# @
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 的最短路径上的中间顶点。