for each vertex v ∈ G.V - {s} v.d = ∞ v.pred = null s.d = 0 for i from 1 to |G.V| - 1 for each edge (u,v) ∈ G.E if u.d + (u,v).w < v.d v.d = u.d + (u,v).w v.pred = u for each edge (u,v) ∈ G.E if u.d + (u,v).w < v.d error "negative-weight cycle"