图论：松弛技术

单源最短路径基于称为松弛的技术, 该方法会反复减小每个顶点的实际最短路径权重的上限, 直到该上限等于最短路径权重。对于每个顶点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