Skip to content

All Pairs Shortest Paths

Summarized notes from Introduction to Algorithms, Chapter 25

  • Can be solved by running single-source shortest path on each vertex
    → works but is slow; we can do better
  • most all-pairs algorithms use adjacency matrix (except Johnson's)
  • find, for every pair of vertices \(u, v \in V\) shortest path from \(u\) to \(v\)
    • input
      • Input is weighted, directed graph \(G = (V, E)\)
      • may have negative weights but no cycles
    • output
      • output in tabular form as \(n \times n\) matrix, \(n = |V|\)
      • \(u\)-row \(v\)-column is shortest path weight from \(u\) to \(v\)
      • another output is predecessor matrix which gives the shortest path from \(i\) to \(j\) if it exists
      • for each vertex we define predecessor subgraph \(G_{\pi, i} = (V_{\pi, i}, E_{\pi, i})\)
        → if \(G_{\pi, i}\) is a shortest path tree, the path can be printed by:
1
2
3
4
5
6
7
PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, j)
    if (i == j)
        print i
    elseif 𝜋ij == NIL
        print "no path from" i "to" j "exits"
    else PRINT-ALL-PAIRS-SHORTEST-PATH(Π, i, 𝜋ij)
        print j

How to Solve All Pairs

-w = weighted

Running time Algo Graph type
\(\Theta(V^3 \lg V)\) Matrix multiplication -w; no -w cycles
\(\Theta(V^3)\) Floyd-Warshall -w; no -w cycles
\(O(V^2 \lg V + VE)\) Johnson's sparse graphs