图论（松弛技术） _松弛技术

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