鬆弛

π[v]代表S到v的當前最短路徑中v點之前的一個點的編號，我們用下面的Θ(V)時間的過程來對最短路徑估計和前趨進行初始化。

INITIALIZE-SINGLE-SOURCE(G,s)

1for each vertex v∈V[G]

2do d[v]←∞

3 π[v]←NIL

4 d[s]←0

經過初始化以後，對所有v∈V，π[v]=NIL，對v∈V-{s}，有d[s]=0以及d[v]=∞。

在鬆弛一條邊(u,v)的過程中，要測試是否可以通過u，對迄今找到的v的最短路徑進行改進；如果可以改進的話，則更新d[v]和π[v]。一次鬆弛操作可以減小最短路徑估計的值d[v]，並更新v的前趨域π[v](S到v的當前最短路徑中v點之前的一個點的編號)。下面的偽代碼對邊(u,v)進行了一步鬆弛操作。

RELAX(u, v, w)

1if(d[v]>d[u]+w(u,v))

2then d[v]←d[u]+w(u,v)

3 π[v]←u

每個單源最短路徑演演算法中都會調用INITIALIZE-SINGLE-SOURCE，然後重複對邊進行鬆弛的過程。另外，鬆弛是改變最短路徑和前趨的唯一方式。各個單源最短路徑演演算法間區別在於對每條邊進行鬆弛操作的次數，以及對邊執行鬆弛操作的次序有所不同。在Dijkstra演演算法以及關於有向無迴路圖的最短路徑演演算法中，對每條邊執行一次鬆弛操作。在Bellman-Ford演演算法中，每條邊要執行多次鬆弛操作。

順帶提一句，鬆弛操作的不等式與差分約束系統有著密不可分的關聯。