Floyd-Warshall ‘s All Pair Shortest Path Algorithm

In the previous two posts, I explained two different algorithms to find the shortest path in the graph. In this post I will define another very simple yet important problem in Graph Theory. Its called the “All Pair Shortest Path” problem.

Given a graph G, as a set of vertices V and directed weighted edges E, the aim of the problem is to find the cost of shortest path between every pair of vertices. Cost of a shortest path is defined as the sum of the edge weights in the shortest paths.

At first sight this problem might look really hard to approach. But the following theorem will make this one of the easiest to approach and especially code it.

Theroem:

If A represents the adjacency matrix of the graph, then for an integer k<=|V| , the (i,j) entry in the matrix A^k , gives the shortest path of length atmost k, between i and j in the original graph.

This above theorem can be easily proved using induction on k. I will leave that as a simple exercise.

From the theorem, all that is left to find is the matrix A^n.

A trivial way to compute this would be to do ‘n’ matrix multiplications. This would take a complexity of O(|V|^4).

Instead, Floyd and Warshall gave a Dynamic Programming based approach.

for k from 1 to n:
    for i from 1 to n:
        for j from 1 to n:
            A[i][j] = min(A[i][j],A[i][k]+A[k][j])

The above algorithm has a very simple intuition. The shortest path from i to j can be either the current value, or sum of shortest path from (i,k) and shortest path from (k,j). Instead of calculating this value repeatedly, we will use a dynamic programming approach and calculate once and store it.

The above algorithm has 3 loop each running for O(|V|) time. Hence the overall complexity is O(|V|^3).

A java implementation of the above algorithm can be found here.

Prim’s Algorithm

In the last post, I defined a spanning tree and gave an algorithm called the ‘Kruskal’s Algorithm’. In this post, I am going to describe another algorithm that also helps in computing the minimum spanning tree of a graph. This algorithm is called the ‘Prim’s Algorithm’ . The basic intuition behind the algorithm goes as follows: Firstly, every vertex should be reachable from every other vertex for it to be a tree. So we will try to build the tree by adding one vertex after another into the connected component. Since we want a “minimum” such tree, we will use the edge between the new vertex and the old component, that is of the minimum weight. This intuition is formalized below as an algorithm:

Set ConnectedSet = Pick a random vertex v of vertex set
Set ToBeAddedSet = set of vertices except vertex v
Set ListOfBridgeEdges = Set of Edges

while ToBeAddedSet not empty:
    - Select the minimum edge e from the ListOfBridgeEdges
       such that it has exactly one end in ConnectedSet

    - Add the other end of e to the ConnectedSet and remove
      it from the ToBeAddedSet

Let us now analyze the complexity of the above algorithm:

1) The outer while loop runs for O(|V|) times.

2) Inside each loop iteration, it takes O(|E|) to select the minimum weighted edge such that it has exactly one end in ConnectedSet.

Therefore the overall running time of this algorithm is O(|V| * |E|). And in the worst case |E| is O(|V|^2). Hence, the worst case running time will be O(|V|^3). We can now improve the above algorithm by using a different data structure to store the bridge edges. We will store the edges in a min priority queue(a heap structure).

- Initialise an empty min priority queue Q.
- Store a <key,value> pair in the queue,where key is the comparator for the queue.

- for all the vertices v in V:
    Initialise the key as infinity
    Initialise the value as NULL

- Choose a random vertex v from V.
  Initialise the key as 0.

- Push v into Q
- while Q is not NULL:
     Assign u as the extract minimum from priority queue Q
     for all v neighbour of u:
         if v is present in Q and edgeweight(u,w)< key value of v:
             Assign v->value as u
             Assign v->key as edgeweight(u,w)

Now using the predecessors information present in the v->value, we can build the MST.

Let us now analyse the complexity of this modified algorithm

1) The outermost while loop runs for O(|V|) iterations.

2) For each iteration, the extract minimum from the priority queue takes O(log |V|). Hence the complexity is O(|V| log |V| ) for L13.

3) To analyse the inner loop is slightly tricky. Notice that the total number of times the outer loop + the inner loop executes is exactly 2*|E|. Because each edge is counted twice. Once for each of its end vertices.

4) Each time inside the inner loop, the value of the key is potentially changed. And to insert this back in the priority queue it takes a complexity of O(log |V|). Hence the inner loop overall takes O(|E| log |V|).

Hence, with this modified algorithm, the overall complexity is O(|V| log |V| + |E| log |V|).  And for |E| = O(|V|^2), the algorithm runs in O(|V|^2 log |V|), which is a improvement over O(|V|^3).

A JAVA implementation of the Prim’s Algorithm can be found here.