# 6.3. Shortest Path Algorithm

# Floyd-Warshall All-Pairs Shortest Path Algorithm

In general, the cost(weight) may be negative, but there must not exist a negative cycle in the graph.

• Problem

  • Given a weighted graph G = (V, E) with cost function cost[i][j], find the shortest paths between all pairs of vertices. V = \{v_0, v_1, v_2, ..., v_{n-1} \} with |V| = n

  • cost[i][j] = 0 if i=j

  • cost[i][j] = c_{ij} if (i,j) \in E(G)

  • cost[i][j] = \infty if (i,j) \notin E(G)

  

• A dynamic programming approach

  • Let A^k [i][j] be the cost of the shortest path from i to j, using only those intermediate vertices with an index ≤ k.

  • The goal is to compute A^{n-1} [i][j] \forall i,j = 0,1,2,...,n-1

    

  • Optimal substructure for computing A^k [i][j] from A^{k-1} [i][j]

    1. If the shortest path from i to j going through no vertex with index greater than k does not go through the vertex with index k A^k [i][j] = A^{k-1} [i][j]

    2. If the shortest path from i to j going through no vertex with index greater than k does go through the vertex with index k A^k [i][j] = $A^ [i][k] + A^ [k][j] $

    

• The table computation

  • Initialization / Table traversal order

  • Example: k = 4 (A_k[i][j] \leftarrow A_{k-1}[i][j])

    

  • O(n^3) time

  • An in-place implementation is possible.

• Path reconstruction

  • ref