All-pairs shortest paths Input: Digraph G=(V, E), where v=n, with edge-weight function w: E>R Output: n x n matrix of shortest-path lengths 6(2 i for all i,j∈ IDEA #1 Run bellman-Ford once from each vertex Time =O(VZE Dense graph→O(4)time Good first try! c 2001 by Charles E Leiserson Introduction to Agorithms Day32L19.3© 2001 by Charles E. Leiserson Introduction to Algorithms Day 32 L19.3 All-pairs shortest paths Input: Digraph G = (V, E), where |V| = n, with edge-weight function w : E → R. Output: n × n matrix of shortest-path lengths δ(i, j) for all i, j ∈ V. IDEA #1: • Run Bellman-Ford once from each vertex. • Time = O(V 2E). • Dense graph ⇒ O(V 4) time. Good first try!