/    /  DAA- All pairs shortest path problem

All pairs shortest path problem

 

All-pairs shortest path problem aims to figure out the shortest path from one vertex to another. We use the all-pairs shortest path to calculate the distance between one node to another as storing all paths individually can be very expensive, as we will need a spanning tree for each individual vertex. 

In this method we use the following three methods for improvement:

  1. Matrix multiplication
  2. Floyd-Warshall method
  3. Johnson O method. 

 

Floyd-Warshall algorithm

We follow the principle of dynamic programming in the Floyd-Watrshall algorithm. The time complexity is determined by the triply nested for loops in the algorithm, and each execution of line 6 takes O(1) time, therefore the total time complexity of the algorithm is θ(n^3). 

The algorithm can be written as follows:

  1. n ← rows [W].
  2. D0 ← W
  3. for k ← 1 to n
  4. do for i ← 1 to n     
  5. do for j ← 1 to n     
  6. do dij(k) ← min (dij(k-1),dik(k-1)+dkj(k-1) )
  7. return D(n)

 

In this algorithm, we start by initializing the solution matrix the same as the input graph matrix. Moving further, we update the solution matrix by taking all the vertices as an intermediate vertex. Basically, we pick all the vertices one by one and update the shortest path. So, when we pick a vertex v as the intermediate vertex it is implied that vertices – {0,1,2,3…, v-1} have already been considered as intermediate vertices. 

 

For every (i, j) there are two possible cases:

  1. v is not the intermediate vertex in the shortest path from i to j, therefore we will keep the distance[i] [j] the same. 
  2. v is the intermediate vertex in the shortest path from i to j, therefore we will update the distance[i] [j] to dist[i] [v] + dist[v] [j], if dist[i][j] > dist[i] [v] + dist[v] [j]. 

 

Johnson’s algorithm

Johnson’s algorithm follows the technique of reweighting and hence can find all the pairs of the shortest path in O(V2log V + VE) time. So, if all the edge weights in a graph are non-negative then we follow Dijkstra’s algorithm to find the shortest path between all pairs of vertices. It will yield better results than the Floyd method, but the problem is it does not work with negative edge weights. So, what is done, is all the weights are re-weighted and made positive, then Dijkstra’s method is used to calculate the shortest path. 

Algorithm:

  1. Start by taking a graph, let it be G. Add new vertices, and modify the graph, let it be known as G’.
  2. Then we use the Bellman-Ford algorithm on the updated graph G’. Let the distances calculated be {0,1,2,3,….,v-1}. If the weight cycle is negative then return. 
  3. Reweight the edges from the original graph. The new weights will be added as the original weight + h[u] – h[v]. 
  4. After reweighting and removing the added vertex, we run Dijkstra’s algorithm. 

 

Reference

All pairs shortest path problem