图论:松弛技术

单源最短路径基于称为松弛的技术, 该方法会反复减小每个顶点的实际最短路径权重的上限, 直到该上限等于最短路径权重。对于每个顶点v∈V, 我们维护一个属性d [v], 它是从源s到v的最短路径权重的上限。我们将d [v]称为最短路径估计。

INITIALIZE - SINGLE - SOURCE (G, s)
 1. for each vertex v ∈ V [G]
 2. do d [v] ← ∞
 3. π [v] ← NIL
 4. d [s] ← 0

初始化后, 对于所有v∈V, π[v] = NIL, 对于v = s d [v] = 0, 对于v∈V-{s} d [v] =∞。

放宽边缘(u, v)的过程包括测试是否可以通过遍历u来改善到目前为止找到的v的最短路径, 如果可以, 则更新d [v]和π[v]。松弛步骤可以减小最短路径估计d [v]和更新的v的前驱场π[v]的值。

图:放宽权重w(u, v)= 2的边(u, v)。每个顶点的最短路径估计出现在顶点内。

松弛技术

(a)因为v。d> u。 d + w(u, v)在松弛之前, v。d的值减小

松弛技术

(b)在这里, v。d <u。 d + w(u, v)在放松边缘之前, 因此放松步骤使v。d保持不变。

后续代码在边(u, v)上执行松弛步骤

RELAX (u, v, w)
 1. If d [v] > d [u] + w (u, v)
 2. then d [v] ← d [u] + w (u, v)
 3. π [v] ← u
微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?