Type INITIALIZE-SINGLE-SOURCE and RELAX

Answer

INITIALIZE-SINGLE-SOURCE(G, s): for each v in G.V: v.d = INF; v.pi = NIL s.d = 0 RELAX(u, v, w): if v.d > u.d + w(u, v): v.d = u.d + w(u, v) v.pi = u

Every shortest-path algorithm is INITIALIZE-SINGLE-SOURCE plus a particular schedule of RELAX calls. RELAX only ever lowers v.d, so the upper-bound property d ≥ δ is maintained throughout.