All-Pairs Shortest Paths (APSP)

1.  Problem Denition

    --  Input: Directed graph G = (V , E) with edge costs ce for each edge e in E, [No distinguished source vertex.]

    --  Goal: Either

        (A) Compute the length of a shortest u --> v path for all pairs of vertices u, v in V

        (B) Correctly report that G contains a negative cycle.

 

2.  Invocations of a single-source shortest-path subroutine

    --  n Dijkstra = O(nm log n) =

        --  O(n^2 log n) if m = O(n)

        --  O(n^3 log n) if m = O(n^2)

    --  n Bellman-Ford = O(n^2m) =

        --  O(n^3) if m = O(n)

        --  O(n^4) if m = O(n^2)

 

3.  Floyd-Warshall algorithm

    --  Running time : O(n^3) algorithm for APSP. Works even with graphs with negative edge lengths.

    --  At least as good as n Bellman-Fords, better in dense graphs.

    --  In graphs with nonnegative edge costs, competitive with n Dijkstra's in dense graphs.

 

4.  Optimal Substructure

    --  Recall: Can be tricky to define ordering on subproblems in graph problems.

    --  Key idea: Order the vertices V = {1, 2, ... , n} arbitrarily. Let V(k) = {1, 2, ... , k}.

    --  Lemma: Suppose G has no negative cycle. Fix source i in V, destination j in V, and k in {1, 2, ... , n}. Let P = shortest (cycle-free) i -j path with all internal nodes in V(k).

    --  Optimal substructure lemma:

        Suppose G has no negative cost cycle. Let P be a shortest (cycle-free) i -j path with all internal

nodes in V(k). Then:

        Case 1: If k not internal to P, then P is a shortest (cycle-free) i -j path with all internal vertices in V(k-1).

        Case 2: If k is internal to P, then: P1 = shortest (cycle-free) i -k path with all internal nodes in

V(k-1) and P2 = shortest (cycle-free) k-j path with all internal nodes in V(k-1)

 

5.  The Floyd-Warshall Algorithm :

    --  Let A = 3-D array (indexed by i , j , k)

    --  Base cases: For all i , j in V:

        A[i , j , 0] = 0 if i = j ; cij if (i , j) in E ; +Infinity if i <> j and (i , j) not in E

        For k = 1 to n

            For i = 1 to n

                For j = 1 to n

                    A[i , j , k] = min { A[i , j , k - 1] [Case 1] , A[i , k , k - 1] + A[k , j , k - 1] [Case 2]

    --  Correctness: From optimal substructure + induction, as usual.

    --  Running time: O(1) per subproblem, O(n^3) overall.

 

6.  Handling Negative Cycle :

    --  Will have A[i , i , n] < 0 for at least one i in V at end of algorithm if the input graph has negative cost cycle.

    --  Reconstruction : Have Floyd-Warshall compute B[i , j ] = max label of an internal node on a shortest i -j path for all i , j in V. ( Reset B[i , j ] = k if 2nd case of recurrence used to compute

A[i , j , k] )  ==> Can use the B[i , j ]'s to recursively reconstruct shortest paths.

 

7.  Johnson's algorithm

    --  Reduces APSP to :

        -- 1 invocation of Bellman-Ford (O(mn) )

        -- n invocations of Dijkstra (O(nm log n))

    --  Running time: O(mn) + O(mn log n) = O(mn log n) (As good as with nonnegative edge lengths)

 

8.  Reweighting :

    --  G = (V , E) is a directed graph with general edge lengths ce. Fix a real number pv for each vertex v in V.

    --  For every edge e = (u , v) of G, ce' = ce + pu - pv , If the s-t path P has length L with the original edge lengths {ce}, P's length with the new edge length {ce'} is :

        Sum(e in P) { ce' } = Sum( e = (u,v) in P ) { ce + pu - pv } = (Sum ( e in P ) {ce} ) + ps - pt

    --  Summary: Reweighting using vertex weights {pv} adds the same amount (namely, ps - pt ) to every s-t path. Reweighting always leaves the shortest path unchanged.

    --  After reweighting by some {pv}, all edge lengths become nonnegative!

 

9.  Johnson's Algorithm:

    --  Input: Directed graph G = (V , E), general edge lengths ce .

    --  (1) Form G' by adding a new vertex s and a new edge (s , v) with length 0 for each v in G.

    --  (2) Run Bellman-Ford on G' with source vertex s. [If B-F detects a negative-cost cycle in G' (which must lie in G), halt + report this.]

    --  (3) For each v in G, define pv = length of a shortest s --> v path in G'.

             For each edge e = (u , v) in G, define ce' = ce + pu - pv.

    --  (4) For each vertex u of G: Run Dijkstra's algorithm in G, with edge lengths {ce'}, with source vertex u, to compute the shortest-path distance d'(u , v) for each v in G.

    --  (5) For each pair u , v in G, return the shortest-path distance d(u , v) := d'(u , v) - pu + pv

    -- Runing time : O(nm log n)

        -- Step (1) , form G' --> O(n)

        -- Step (2) , run BF --> O(mn)

        -- Step (3), form c' --> O(m)

        -- Step (4), n Dijkstra --> O(nm log n)

        -- Step (5), O(1) work per u-v pair --> O(n2)

 

10.  Correctness of Johnson's Algorithm

    --  Claim: For every edge e = (u , v) of G, the reweighted length ce' = ce + pu - pv is nonnegative.

      --  Proof: Fix an edge (u , v). By construction,

       pu = length of a shortest s-u path in G'

       pv = length of a shortest s-v path in G'

       Let P = a shortest s-u path in G' (with length pu --> exists, by construction of G')

       ==> P + (u , v) = an s-v path with length pu + cuv

       ==> Shortest s-v path only shorter, so pv <= pu + cuv

       ==> c'uv = cuv + pu - pv >= 0.