Algorithm Analysis Spring 2025 | All-Pairs Shortest Paths - CSCE 411

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

Single-Source Shortest Path Problem Summary. problem instance: (G, s, t) or (G, s)

Single-Source Shortest Path Problem Summary. problem instance: (G, s, t) or (G, s) 1. If the graph has no negative edges, then apply Dijkstra s algorithm, which takes time no more than O(m log n) and O(n2).

Single-Source Shortest Path Problem Summary. problem instance: (G, s, t) or (G, s) 1. If the graph has no negative edges, then apply Dijkstra s algorithm, which takes time no more than O(m log n) and O(n2). 2. If the graph is undirected and has negative edges that are reachable from s, then the problem has no meaningful solutions.

Single-Source Shortest Path Problem Summary. problem instance: (G, s, t) or (G, s) 1. If the graph has no negative edges, then apply Dijkstra s algorithm, which takes time no more than O(m log n) and O(n2). 2. If the graph is undirected and has negative edges that are reachable from s, then the problem has no meaningful solutions. Remark: all conditions in 1 and 2 can be easily detected.

Single-Source Shortest Path Problem Summary. problem instance: (G, s, t) or (G, s) 1. If the graph has no negative edges, then apply Dijkstra s algorithm, which takes time no more than O(m log n) and O(n2). 2. If the graph is undirected and has negative edges that are reachable from s, then the problem has no meaningful solutions. Remark: all conditions in 1 and 2 can be easily detected. 3. If the graph is directed and has negative edges, then apply Bellman-Ford algorithm that runs in time O(nm), and either reports negative cycles or returns shortest paths from s.

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

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). First Solution. For each vertex s, call Bellman-Ford to find shortest paths from s to all other vertices. Time = O(n2m) = O(n4)

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). First Solution. For each vertex s, call Bellman-Ford to find shortest paths from s to all other vertices. Time = O(n2m) = O(n4) We want to do better. This time we use adjacency matrices.

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). First Solution. For each vertex s, call Bellman-Ford to find shortest paths from s to all other vertices. Time = O(n2m) = O(n4) We want to do better. This time we use adjacency matrices.

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). First Solution. For each vertex s, call Bellman-Ford to find shortest paths from s to all other vertices. Time = O(n2m) = O(n4) We want to do better. This time we use adjacency matrices. For each k, define an n x n matrix M(k) = [dij(k)]1 i n,1 j n, where dij(k) = the length of the shortest path from i to j that uses only vertices in {1, , k} for its internal vertices

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). First Solution. For each vertex s, call Bellman-Ford to find shortest paths from s to all other vertices. Time = O(n2m) = O(n4) We want to do better. This time we use adjacency matrices. For each k, define an n x n matrix M(k) = [dij(k)]1 i n,1 j n, where dij(k) = the length of the shortest path from i to j that uses only vertices in {1, , k} for its internal vertices M = M(0), M(n) = the matrix for all-pairs shortest paths.

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). First Solution. For each vertex s, call Bellman-Ford to find shortest paths from s to all other vertices. Time = O(n2m) = O(n4) We want to do better. This time we use adjacency matrices. For each k, define an n x n matrix M(k) = [dij(k)]1 i n,1 j n, where dij(k) = the length of the shortest path from i to j that uses only vertices in {1, , k} for its internal vertices M = M(0), M(n) = the matrix for all-pairs shortest paths. How do we compute M(k) from M(k-1)? dij(k) = min{dij(k-1), dik(k-1) + dkj(k-1)}

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). First Solution. For each vertex s, call Bellman-Ford to find shortest paths from s to all other vertices. Time = O(n2m) = O(n4) We want to do better. This time we use adjacency matrices. For each k, define an n x n matrix M(k) = [dij(k)]1 i n,1 j n, where dij(k) = the length of the shortest path from i to j that uses only vertices in {1, , k} for its internal vertices M = M(0), M(n) = the matrix for all-pairs shortest paths. How do we compute M(k) from M(k-1)? dij(k) = min{dij(k-1), dik(k-1) + dkj(k-1)} Thus, starting from M(0)= M, we can compute M(1), M(2), , M(n), where M(n) gives all-pairs shortest paths.

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). Floyd-Warshall(M) 1. M(0)= M; \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); else dij(k) = dik(k-1) + dkj(k-1); 3. return the matrix M(n). dij(k) = min{dij(k-1), dik(k-1) + dkj(k-1)}

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); else dij(k) = dik(k-1) + dkj(k-1); 3. return the matrix M(n).

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); else dij(k) = dik(k-1) + dkj(k-1); 3. return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k).

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); else dij(k) = dik(k-1) + dkj(k-1); 3. return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k). pij(k) j i the path of length dij(k) connecting i and j.

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; initialize P(0); \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); else dij(k) = dik(k-1) + dkj(k-1); 3. Return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k). For P(0) = [pij(0)], pij(0) = i if [i, j] is an edge, and pij(0) = NIL otherwise. pij(k) j i the path of length dij(k) connecting i and j.

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; initialize P(0); \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); pij(k) = pij(k-1); else dij(k) = dik(k-1) + dkj(k-1); pij(k) = pkj(k-1); 3. Return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k). For P(0) = [pij(0)], pij(0) = i if [i, j] is an edge, and pij(0) = NIL otherwise. pij(k) j pkj(k-1) k i i j the path of length dij(k) connecting i and j. dik(k-1) dkj(k-1)

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; initialize P(0); \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); pij(k) = pij(k-1); else dij(k) = dik(k-1) + dkj(k-1); pij(k) = pkj(k-1); 3. Return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k). For P(0) = [pij(0)], pij(0) = i if [i, j] is an edge, and pij(0) = NIL otherwise. Print(P(n), i, j) 1. k = j; 2. while (k i) print(k); k = pik(n); 3. print(k) With P(n) = [pij(n)], for any vertex pair i and j, we can print out the shortest path from i to j backwards.

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; initialize P(0); \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); pij(k) = pij(k-1); else dij(k) = dik(k-1) + dkj(k-1); pij(k) = pkj(k-1); 3. Return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k). Theorem. Floyd-Warshall solves the All-Pairs Shortest Paths Problem in time O(n3) and space O(n2).

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; initialize P(0); \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); pij(k) = pij(k-1); else dij(k) = dik(k-1) + dkj(k-1); pij(k) = pkj(k-1); 3. Return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k). Theorem. Floyd-Warshall solves the All-Pairs Shortest Paths Problem in time O(n3) and space O(n2). Compared to the approach we proposed based on Bellman-Ford: time O(n2m) = O(n4) and space O(m) = O(n2).

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; initialize P(0); \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); pij(k) = pij(k-1); else dij(k) = dik(k-1) + dkj(k-1); pij(k) = pkj(k-1); 3. Return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k). Theorem. Floyd-Warshall solves the All-Pairs Shortest Paths Problem in time O(n3) and space O(n2). What if there are negative cycles?

All-Pairs Shortest Paths Problem Problem. Given a (possibly negatively) weighted graph G in an adjacency matrix M, find the shortest path from s to t for all vertex pairs (s, t). The matrix only gives the length of the shortest path for each vertex pair. How do we get the actual shortest path for each vertex pair? Floyd-Warshall(M) 1. M(0)= M; initialize P(0); \\ M(0) = [dij(0)] 2. for (k = 1; k n; k++) \\ compute M(k) = [dij(k)] from M(k-1) = [dij(k-1)] 2.1 for (i = 1; i n; i++) 2.2 for (j = 1; j n; j++) if (dij(k-1) < dik(k-1) + dkj(k-1)) dij(k) = dij(k-1); pij(k) = pij(k-1); else dij(k) = dik(k-1) + dkj(k-1); pij(k) = pkj(k-1); 3. Return the matrix M(n). Use another group of matrices P(k) = [pij(k)], where pij(k) is the vertex right before j on the shortest path from i to j for the matrix M(k). Theorem. Floyd-Warshall solves the All-Pairs Shortest Paths Problem in time O(n3) and space O(n2). What if there are negative cycles? If a vertex v is in a negative cycle, then M(n)[v, v] < 0.