Shortest Paths and Transitive Closure

Let G = (V, E) be an undirected graph and let ℓ be a function assigning a nonnegative length to each edge. Extend ℓ to domain V x V by defining ℓ(υ, υ) = 0 and ℓ(u, υ) = ∞ if (u, υ) ∉ E. Define the length2 of a path $$ p = {e_{1}}{e_{2}}...{e_{n}}{\text{ to be }}l(p) = \Sigma _{{i = 1}}^{n}l({e_{i}}). $$. For u, υ ∈ V, define the distanced(u, υ) from u to υ to be the length of a shortest path from u to υ, or ∞ if no such path exists. The single-source shortest path problem is to find, given s ∈ V, the value of d(s, u) for every other vertex u in the graph.