All Pairs Shortest Path (Floyd-Warshall) Algorithm

All Pairs Shortest Path Algorithm – Introduction

All Pairs Shortest Path Algorithm is also known as the Floyd-Warshall algorithm. And this is an optimization problem that can be solved using dynamic programming.

Let G = <V, E> be a directed graph, where V is a set of vertices and E is a set of edges with nonnegative length. Find the shortest path between each pair of nodes.

L = Matrix, which gives the length of each edge

L[i, j] =   0, if i == j // Distance of node from itself is zero

L[i, j] =  ∞ , if i ≠ j and (i, j) ∉ E

L[i, j] = w (i, j), if i ≠ j and (i, j) ∈ E  // w(i, j) is the weight of the edge (i, j)

Principle of optimality :

If k is the node on the shortest path from i to j, then the path from i to k and k to j, must also be shortest.

In the following figure, the optimal path from i to j is either p or summation of p₁ and p₂.

While considering k^th vertex as intermediate vertex, there are two possibilities :

• If k is not part of shortest path from i to j, we keep the distance D[i, j] as it is.
• If k is part of shortest path from i to j, update distance D[i, j] as
  D[i, k] + D[k, j].

Optimal sub structure of the problem is given as :

D^k [i, j] = min{ D^{k – 1} [i, j], D^{k – 1} [i, k] + D^{k – 1} [k, j] }

D^k = Distance matrix after k^th iteration

Algorithm for All Pairs Shortest Path

This approach is also known as the Floyd-warshall shortest path algorithm. The algorithm for all pair shortest path (APSP) problem is described below

Algorithm FLOYD_APSP ( L)
// L is the matrix of size n  n representing original graph
// D is the distance matrix

D ← L
for k ← 1 to n do
    for i ← 1 to n do
        for j ← 1 to n do
            D[i, j]k ← min ( D[i, j]k-1, D[i, k]k-1 + D[k, j]k-1 )
        end
    end
end
return D

Complexity analysis of All Pairs Shortest Path Algorithm

It is very simple to derive the complexity of all pairs’ shortest path problem from the above algorithm. It uses three nested loops. The innermost loop has only one statement. The complexity of that statement is Q(1).

The running time of the algorithm is computed as :

Example

Problem: Apply Floyd’s method to find the shortest path for the below-mentioned all pairs.

Solution:

Optimal substructure formula for Floyd’s algorithm,                                

D^k [i, j] = min { D^{k – 1} [i, j], D^{k – 1} [i, k] + D^{k – 1} [k, j] }

Iteration 1 : k = 1 :

D¹[1, 2] = min { D^o [1, 2], D^o [1, 1] + D^o [1, 2] }

= min {∞, 0 + ∞} 

=  ∞

D¹[1, 3] = min { D^o [1, 3], D^o [1, 1] + D^o [1, 3] }

= min {3, 0 + 3} 

= 3

D¹[1, 4] = min { D^o [1, 4], D^o [1, 1] + D^o [1, 4] }

= min {∞, 0 + ∞} 

=  ∞

D¹[2, 1] = min { D^o [2, 1], D^o [2, 1] + D^o [1, 1] }

= min {2, 2 + 0} 

= 2

D¹[2, 3] = min { D^o [2, 3], D^o [2, 1] + D^o [1, 3] }

= min {∞, 2 + 3} 

= 5

D¹[2, 4] = min { D^o [2, 4], D^o [2, 1] + D^o [1, 4] }

= min {∞, 2 + ∞} 

= ∞

D¹[3, 1] = min { D^o [3, 1], D^o [3, 1] + D^o [1, 1] }

= min {∞, 0 + ∞} 

= ∞

D¹[3, 2] = min { D^o [3, 2], D^o [3, 1] + D^o [1, 2] }

= min {7, ∞ + ∞} 

= 7

D¹[3, 4] = min { D^o [3, 4], D^o [3, 1] + D^o [1, 4] }

= min {1, ∞ + ∞} 

= 1

D¹[4, 1] = min { D^o [4, 1], D^o [4, 1] + D^o [1, 1] }

= min {6, 6 + 0} 

= 6

D¹[4, 2] = min { D^o [4, 2], D^o [4, 1] + D^o [1, 2] }

= min {∞, 6 + ∞} 

= ∞

D¹[4, 3] = min { D^o [4, 3], D^o [4, 1] + D^o [1, 3] }

= min {∞, 6 + 3} 

= 9

Note : Path distance for highlighted cell is improvement over original matrix.

Iteration 2 (k = 2) :

D²[1, 2] = D¹ [1, 2]  =  ∞

D²[1, 3] = min { D¹ [1, 3], D¹ [1, 2] + D¹ [2, 3] }

= min {3, ∞ + 5} 

= 3

D²[1, 4] = min { D¹ [1, 4], D¹ [1, 2] + D¹ [2, 4] }

= min {∞, ∞ + ∞} 

= ∞

D²[2, 1] = D¹ [2, 1]  =  2

D²[2, 3] = D¹ [2, 3]  =  5

D²[2, 4] = D¹ [2, 4]  =  ∞

D²[3, 1] = min { D¹ [3, 1], D¹ [3, 2] + D¹ [2, 1] }

= min {∞, 7 + 2} 

= 9

D²[3, 2] = D¹ [3, 2]  =  7

D²[3, 4] = min { D¹ [3, 4], D¹ [3, 2] + D¹ [2, 4] }

= min {1, 7 + ∞} 

= 1

D²[4, 1] = min { D¹ [4, 1], D¹ [4, 2] + D¹ [2, 1] }

= min {6, ∞ + 2} 

= 6

D²[4, 2] = D¹ [4, 2]  =  ∞                                

D²[4, 3]  =  min { D¹ [4, 3], D¹ [4, 2] + D¹ [2, 3] }

= min {9, ∞ + 5} 

= 9

Iteration 3 (k = 3) :

D³[1, 2] = min { D² [1, 2], D² [1, 3] + D² [3, 2] }

= min {∞, 3 + 7} 

= 10

D³[1, 3] = D² [1, 3]  =  3

D³[1, 4] = min { D² [1, 4], D² [1, 3] + D² [3, 4] }

= min {∞, 3 + 1} 

= 4

D³[2, 1] = min { D² [2, 1], D² [2, 3] + D² [3, 1] }

= min {2, 5 + 9} 

= 2

D³[2, 3] = D² [2, 3]  =  5

D³[2, 4] = min { D² [2, 4], D² [2, 3] + D² [3, 4] }

= min {∞, 5 + 1} 

= 6

D³[3, 1] = D² [3, 1]  =  9

D³[3, 2] = D² [3, 2]  =  7

D³[3, 4] = D² [3, 4]  =  1

D³[4, 1] = min { D² [4, 1], D² [4, 3] + D² [3, 1] }

= min {6, 9 + 9} 

= 6

D³[4, 2] = min { D² [4, 1], D² [4, 3] + D² [3, 2] }

= min {∞, 9 + 7} 

= 16

D³[4, 3] = D² [4, 3]  =  9

Iteration 4 (k = 4) :

D⁴[1, 2] = min { D³ [1, 2], D³ [1, 4] + D³ [4, 2] }

= min {10, 4 + 16} 

= 10

D⁴[1, 3] = min { D³ [1, 3], D³ [1, 4] + D³ [4, 1] }

= min {3, 4 + 9} 

= 3

D⁴[1, 4] = D³ [1, 4]  =  4

D⁴[2, 1] = min { D³ [2, 1], D³ [2, 4] + D³ [4, 1] }

= min {2, 6 + 6} 

= 2

D⁴[2, 3] = min { D³ [2, 3], D³ [2, 4] + D³ [4, 3] }

= min {5, 6 + 9} 

= 5

D⁴[2, 4] = D³ [2, 4]  =  6

D⁴[3, 1] = min { D³ [3, 1], D³ [3, 4] + D³ [4, 1] }

= min {9, 1 + 6} 

= 7

D⁴[3, 2] = min { D³ [3, 2], D³ [3, 4] + D³ [4, 2] }

= min {7, 1 + 16} 

= 7

D⁴[3, 4] = D³ [3, 4]  =  1

D⁴[4, 1] = D³ [4, 1]  =  6

D⁴[4, 2] = D³ [4, 2]  = 16

D⁴[4, 3] = D³ [4, 3]  =  9

Final distance matrix is,

Problem: Obtain all pair shortest path using Floyd’s Algorithm for given weighted graph

Solution:

Optimal substructure formula for Floyd’s algorithm,

D^k [i,j] = min{ D^{k – 1} [i, j], D^{k – 1} [i, k] + D^{k – 1} [k, j] }

Iteration 1 (k = 1) :

D¹ [1, 2] = min {D⁰[1, 2], D⁰[1, 1] + D⁰[1, 2] }

= min {8, 0 + 8}

= 8

D¹[1, 3] = min {D⁰[1, 3], D⁰[1, 1] + D⁰[1, 3] }

= min {5, 0 + 5}

= 5

D¹[2, 1] = min {D⁰[2, 1], D⁰[2, 1] + D⁰[1, 1] }

= min {2, 2 + 0}

= 2

D¹[2, 3] = min {D⁰[2, 3], D⁰[2, 1] + D⁰[1, 3] }

= min {∞, 2 + 5}

= 7

D¹[3, 1] = min {D⁰[3, 1], D⁰[3, 1] + D⁰[1, 1] }

= min {∞, ∞ + 0}

= ∞

D¹[3, 2] = min {D⁰[3, 2], D⁰[3, 1] + D⁰[1, 2] }

= min {1, 1 + 8}

= 1

Iteration 2 (k = 2) :

D²[1, 2] = min {D¹[1, 2],  D¹[1, 2] + D¹[2, 2]}

= min {8, 8 + 0}

= 8

D²[1, 3] = min {D¹[1, 3], D¹[1, 2] +  D¹[2, 3] }

= min {5, 8 +7}

= 5

D²[2, 1] = min {D¹[2, 1], D¹[2, 2] + D¹[2, 1}

=  min {2, 0 + 2}

= 2

D²[2, 3] = min {D¹[2, 3], D¹[2, 2] + D¹[2, 3] }

=  min {7, 0 + 7}

= 7

D²[3, 1] = min {D¹[3, 1], D¹[3, 2] + D¹[2, 1] }

= min {∞, 1 + 2}

= 3

D²[3, 2] = min {D¹[3, 2], D¹[3, 2] + D¹[2, 2] }

= min {1, 1 + 0}

= 1

Iteration 3 (k = 3) :

D³[1, 2] = min {D²[1, 2],  D²[1, 3] + D²[3, 2]}

= min {8, 5 + 1}

= 6

D³[1, 3] = min {D²[1, 3], D²[1, 3] +  D²[3, 3] }

= min {5, 5 + 0}

= 5

D³[2, 1] = min {D²[2, 1], D²[2, 3] + D²[3, 1}

= min {2, 7 + 3}

= 2

D³[2, 3] = min {D²[2, 3], D²[2, 3] + D²[3, 3] }

= min {7, 7 + 0}

= 7

D³[3, 1] = min {D²[3, 1], D²[3, 3] + D²[3, 1] }

= min {3, 0 + 3}

= 3

D³[3, 2] = min {D²[3, 2], D²[3, 3] + D²[3, 2] }

= min {1, 0 + 1}

= 1

Some Popular Problems Solved using Dynamic Programming

• Binomial Coefficient
• Making a Change
• Knapsack Problem
• Multistate Graph Problem
• Optimal Binary Search Tree
• Matrix Chain Multiplication
• Longest Common Subsequence
• Bellman-Ford (Single Source Shortest Path) Algorithm
• Floyd-Warshall (All Pair Shortest Path) Problem
• Assembly Line Scheduling
• Travelling Salseman Problem
• Flow Shop Scheduling

---

Additional Reading: Fast Implementation