查看: 1087|回复: 0

节点最短路径算法改进

字体大小: 正常放大

1175 主题	4 听众	2823 积分

该用户从未签到

电梯直达

1^#

发表于 2024-10-23 16:12 |只看该作者 |倒序浏览

|招呼Ta 关注Ta

实现了一种基于邻接矩阵的图算法，具体是 Floyd-Warshall 算法的一个变种，用于计算每对节点之间的最短路径。下面对代码进行逐行分析并解释算法思想。

Floyd-Warshall 算法的基本思想Floyd-Warshall 算法是一种用于求解加权图中任意两点之间最短路径的动态规划算法。它的思想是通过中间节点逐步更新路径长度，最终得到所有节点对之间的最短路径。
代码解析

[color=rgba(6, 8, 31, 0.88)]函数定义:

function a = dij2_m(a)

复制代码

- `a` 为输入的邻接矩阵，表示图中节点之间的边的权重。
- 输出结果也是更新后的邻接矩阵 `a`，其中的值代表任意两节点之间的最短路径距离。

[color=rgba(6, 8, 31, 0.88)]将邻接矩阵变为对称矩阵[color=rgba(6, 8, 31, 0.88)]:

n = length(a);
' M. F* `/ G: K, E( e
for i = 2:n - ?, h1 s! G4 l6 J
for j = 1:(i-1)
, P ]( N. U; q s0 \- l
a(i,j) = a(j,i); 4 W4 O6 Q: G- W' R8 \, v
end 3 K. e- |* a* O
end

复制代码

- 这部分代码确保输入的邻接矩阵是对称的，即 $a(i, j) = a(j, i)$。这是因为对于无向图，节点间的距离应该是相同的。

[color=rgba(6, 8, 31, 0.88)]主程序[color=rgba(6, 8, 31, 0.88)]:

for k = 1:(n-1)
# J7 p: c2 N7 l* i C2 ?
b = [1:(k-1),(k+1):n]; % 初始化剩余节点
6 S\" [' U\" U6 N- m# G4 R# q( W7 ~
kk = length(b);
# l: ^1 x9 h( _\" T/ b; Z* ]
a_id = k; % 当前节点 5 Z* s8 |! I2 n
b1 = [(k+1):n]; % 节点的一部分
9 P$ S) _6 h. q) b0 k
kk1 = length(b1);

复制代码

- 这段代码是在外层循环中执行的。变量 `k` 表示当前考虑的中间节点。
- `b` 是未考虑的节点集合，初始为包含所有节点（除了当前节点 `k`）的数组。
- `b1` 是一组要更新的节点，将从 `k+1` 开始划分，以找到与节点 `k` 的路径。

[color=rgba(6, 8, 31, 0.88)]更新最短路径[color=rgba(6, 8, 31, 0.88)]:

while kk > 0
$ s8 F, y; V2 t2 G5 u5 r
for j = 1:kk1
4 q8 o7 I\" w+ {\" W
te = a(k, a_id) + a(a_id, b1(j)); ! c8 s; K4 w% a
if te < a(k, b1(j))
. @( B/ l9 ^4 D! F! r& J+ D
a(k, b1(j)) = te;
2 l% _+ h. {5 k) c
end
% b z3 N3 X% t0 T1 Z3 a( T% x2 W
end

复制代码

- 在 `while` 循环中，对于每个未访问节点，从当前节点 `k` 到所有在 `b1` 中节点的路径进行更新。
- 计算通过当前节点 `a_id` 访问 `b1` 中的每个节点的路径 `te`，如果这个新路径比已知的更短，就更新邻接矩阵。

[color=rgba(6, 8, 31, 0.88)]选择下一个节点[color=rgba(6, 8, 31, 0.88)]:

miid = 1;
! x0 l% ]) [3 h3 p1 o w
for j = 2:kk
+ W7 ~3 V/ k6 k7 z
if a(k, b(j)) < a(k, b(miid))
& \2 H( e. K9 G3 F8 Q# a
miid = j; ) ^\" v( o. ?5 D+ Z
end 3 F) f! Z: Y, p
end
X J7 v- x% Q6 p9 o
a_id = b(miid); % 选取出最短路径的节点
5 O) U\" [9 q6 _7 x8 { f g
b = [b(1:(miid-1)), b((miid+1):kk)]; % 从该集合中移除选择的节点 5 e2 X\" Z! W3 x7 n K$ M
kk = length(b);

复制代码

- 找到当前未访问节点中与 `k` 相连的最短距离节点，将其标记为 `a_id`，并更新集合 `b`，剔除已经访问的节点。

[color=rgba(6, 8, 31, 0.88)]更新所有节点间的距离[color=rgba(6, 8, 31, 0.88)]:

for j = (k+1):n \" ~; ?' w! i3 D9 q; f: i
a(j, k) = a(k, j); ) ~: v( q: R. j* j# h/ t
end

复制代码

- 更新 `a` 中关于节点 `k` 的距离，保证后续节点间的对称性。

总结整体来看，这段代码通过逐步选择中间节点，并更新已处理节点之间的最短路径距离，从而计算出无向图的任意两点之间的最短路径。其核心思想是动态规划和“逐步逼近”，和传统的 Floyd-Warshall 算法有相似之处，但实现上有所变化。

此算法的时间复杂度为 $O(V^3)$，其中 $V$ 是图中节点的数量，适合用于小型图的最短路径计算。