Content #
For each vertex v, the single-source shortest paths algorithms maintain an attribute v.d, which is an upper bound on the weight of a shortest path from source s to v.
The process of relaxing an edge (u,v) consists of testing whether going through vertex u improves the shortest path to vertex v found so far and, if so, updating v.d and v.π.
RELAX(u, v, w)
if v.d > u.d + w(u, v)
v.d = u.d + w(u, v)
v.π = u
