Advanced Algorithms: All-Pairs Shortest Paths Problem Solutions

CSCE-411 Design and Analysis of Algorithms Spring 2025 Instructor: Jianer Chen Office: PETR 428 Phone: 845-4259 Email: chen@cse.tamu.edu Notes 24: Johnson s algorithm for All-Pairs Shortest Paths

All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t).

All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Floyd-Warsall algorithm solves the APSP problem in time O(n3).

All-Pairs Shortest Paths (APSP) Problem. Given a (possibly negatively) weighted graph G, find the shortest path from s to t for all vertex pairs (s, t). Floyd-Warsall algorithm solves the APSP problem in time O(n3). If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse.

All-Pairs Shortest Paths (APSP) If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse.

All-Pairs Shortest Paths (APSP) If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse. However, this does not work when the graph has negative edges.

All-Pairs Shortest Paths (APSP) If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse. However, this does not work when the graph has negative edges. Can we do something , such as adding something to each edge to eliminate negative edges?

All-Pairs Shortest Paths (APSP) If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse. However, this does not work when the graph has negative edges. Can we do something , such as adding something to each edge to eliminate negative edges? For example, add the same value to each edge?

All-Pairs Shortest Paths (APSP) If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse. However, this does not work when the graph has negative edges. Can we do something , such as adding something to each edge to eliminate negative edges? For example, add the same value to each edge? -2 3 4 1 1 1 s t 1 8 -3

All-Pairs Shortest Paths (APSP) If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse. However, this does not work when the graph has negative edges. Can we do something , such as adding something to each edge to eliminate negative edges? For example, add the same value to each edge? -2 3 4 1 1 1 s t 1 8 -3

All-Pairs Shortest Paths (APSP) If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse. However, this does not work when the graph has negative edges. Can we do something , such as adding something to each edge to eliminate negative edges? For example, add the same value to each edge? -2 1 7 3 6 4 1 4 1 4 1 4 s t 1 4 0 11 8 -3 The shortest path in the original graph is no longer a shortest path in the new graph!!!

All-Pairs Shortest Paths (APSP) If the graph G has no negative edges, we can apply Dijkstra s algorithm on each vertex, which solves the APSP problem in time O(nm log n), which is better than O(n3) when the graph is sparse. However, this does not work when the graph has negative edges. Can we do something , such as adding something to each edge to eliminate negative edges? For example, add the same value to each edge? -2 1 7 3 6 4 1 4 1 4 1 4 s t 1 4 0 11 8 -3 The shortest path in the original graph is no longer a shortest path in the new graph!!! Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Does such a change exist?

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Does such a change exist? Consider ANY function h mapping from vertices to real numbers.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Does such a change exist? Consider ANY function h mapping from vertices to real numbers. Define new edge weights wt from the old edge weights wt: wt [u, v] = wt[u, v] + h(u) h(v).

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Does such a change exist? Consider ANY function h mapping from vertices to real numbers. Define new edge weights wt from the old edge weights wt: wt [u, v] = wt[u, v] + h(u) h(v). Theorem. For any path P from s to t: wt [P] = wt[P] + h(s) h(t).

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Does such a change exist? Consider ANY function h mapping from vertices to real numbers. Define new edge weights wt from the old edge weights wt: wt [u, v] = wt[u, v] + h(u) h(v). Theorem. For any path P from s to t: wt [P] = wt[P] + h(s) h(t). Thus, a shortest s-t path in the old graph remains shortest in the new graph, and negative cycles remain negative.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. Does such a change exist? Consider ANY function h mapping from vertices to real numbers. Define new edge weights wt from the old edge weights wt: wt [u, v] = wt[u, v] + h(u) h(v). Theorem. For any path P from s to t: wt [P] = wt[P] + h(s) h(t). Thus, a shortest s-t path in the old graph remains shortest in the new graph, and negative cycles remain negative. We have achieved Conditions 1-2 (for any function h). In order to make Condition 3, we need to pick a good function h.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G.

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G. -2 The graph G -1 -3 4 3 1 1 1 4

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G. -2 The graph G+ 0 -1 -3 4 3 0 1 1 0 0 1 0 4 z 0

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G. (G+ does not eliminate/create negative cycles, and has the same shortest path from any s to t for s, t z). -2 The graph G+ 0 -1 -3 4 3 0 1 1 0 0 1 0 4 z 0

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G. (G+ does not eliminate/create negative cycles, and has the same shortest path from any s to t for s, t z). Step 2. For each vertex v, let h(v) = dist+(z, v) be the distance from z to v in G+. -2 The graph G+ 0 -1 -3 4 3 0 1 1 0 0 1 0 4 z 0

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G. (G+ does not eliminate/create negative cycles, and has the same shortest path from any s to t for s, t z). Step 2. For each vertex v, let h(v) = dist+(z, v) be the distance from z to v in G+. -2 The graph G+ 0 -1 dist+(z, v) can be computed for all v by a single Bellman-Ford. -3 4 3 0 1 1 0 0 1 0 4 z 0

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G. (G+ does not eliminate/create negative cycles, and has the same shortest path from any s to t for s, t z). Step 2. For each vertex v, let h(v) = dist+(z, v) be the distance from z to v in G+. dist+(z, v) can be computed for all v by a single Bellman-Ford. -2 The graph G+ 0 -1 -3 4 3 0 1 1 For any edge [u, v] in G+, because dist+(z, v) dist+(z, u) + wt+(u, v), i.e., h(v) h(u) + wt+(u, v), So 0 0 1 0 4 z 0

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G. (G+ does not eliminate/create negative cycles, and has the same shortest path from any s to t for s, t z). Step 2. For each vertex v, let h(v) = dist+(z, v) be the distance from z to v in G+. dist+(z, v) can be computed for all v by a single Bellman-Ford. -2 The graph G+ 0 -1 -3 4 3 0 1 1 For any edge [u, v] in G+, because dist+(z, v) dist+(z, u) + wt+(u, v), i.e., h(v) h(u) + wt+(u, v), So 0 0 1 0 4 z wt (u, v) = wt+(u, v) + h(u) h(v) 0. 0

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. For any h, let new edge weight wt from the old wt be wt [u, v] = wt[u, v] + h(u) h(v). This edge change wt satisfies Conditions 1-2. Step 1. To pick a function h to make Condition 3 satisfied, we construct a new graph G+ from the old G, by adding a new vertex z plus edges of weight 0 from z to all vertices in G. (G+ does not eliminate/create negative cycles, and has the same shortest path from any s to t for s, t z). Step 2. For each vertex v, let h(v) = dist+(z, v) be the distance from z to v in G+. dist+(z, v) can be computed for all v by a single Bellman-Ford. -2 The graph G+ 0 -1 -3 4 3 0 1 1 For any edge [u, v] in G+, because dist+(z, v) dist+(z, u) + wt+(u, v), i.e., h(v) h(u) + wt+(u, v), So 0 0 1 0 4 z wt (u, v) = wt+(u, v) + h(u) h(v) 0. 0 Let G be the graph G+ with weights wt , G has no negative edges, satisfying Condition 3!

All-Pairs Shortest Paths (APSP) Idea: adding something to edges to eliminate negative edges. Condition 1: The change must keep the shortest paths in the original graph the shortest in the new graph. Condition 2: The change must not eliminate/create negative cycles. Condition 3: The change give no negative weights to edges. To summarize, 1. construct the graph G+ by adding the vertex z and all edges from z; 2. use Bellman-Ford to compute dist+(z, v) in G+ for all vertices v, and let h(v) = dist+(z, v); 3. construct the graph G by reweighting edges [u, v] in G+: wt (u, v)=wt+(u, v)+h(u) h(v); 4. use Dijkstra to solve the APSP problem for G ; 5. Get the APSP solution to G.