8.15

Idea. The distance to a fixed vertex [math]v[/math] in the original digraph equals the distance from [math]v[/math] in the graph whose arcs are reversed. Hence we can solve a single-source problem on the reversed(G) once, instead of |V| single-source runs on the original graph.

Algorithm (non-negative weights).

INPUT : directed graph G=(V,E,w≥0), destination t OUTPUT: d[u] = shortest-path length u→t for every u∈V 1 build R = reversed(G) // for each (u, v) in G add (v, u) with same w 2 run Dijkstra(R, source = t) // ordinary min-priority-queue version 3 return the distance array d[·] // d[u] in R equals distance u→t in G

Time: O(E + V log V) with a binary heap (or O(E + V) using a radix/Fib. heap).

Algorithm (weights may be negative, no negative cycles reachable from t). Replace step 2 by a Bellman–Ford (or SPFA) run starting from t on R; complexity O(VE) in the worst case.

Correctness proof sketch.
For any u, a path u→t in G corresponds one-to-one with a path t→u in R of identical length, and vice-versa. Therefore the minimum-length path u→t equals the minimum-length path t→u in R, so the distances returned by the single-source algorithm on R are exactly the desired single-destination distances in G.

Thus a single run of a standard shortest-path routine on the edge-reversed graph solves the single-destination shortest-paths problem optimally.

Back to Chapter 8