Data Structures and Algorithms: Weighted Graph Processing — Floyd Warshall Algorithm

Floyd Warshall algorithm is a well-known algorithm for the problem — ‘All-pairs shortest path’. It’s a pretty similar problem to the ‘Single source shortest path’ problem which is solved using Dijkstra’s algorithm. Before jumping into the algorithm, let’s first take a look at the problem in hand, ‘All-pairs shortest path’, and how it’s different from the other problem solved using Dijkstra’s.

All Pairs Shortest Path

Floyd Warshall Algorithm

The problem is to find the shortest distances between every pair of vertices in a given weighted graph. If you remember the ‘Single source shortest path’ problem you may notice that it’s just an expansion of the same problem. It’s like running Dijkstra’s algorithm on every vertex of the graph.

So, you may wonder ‘Okay, what is the difference between Floyd Warshall's algorithm and Dijkstra's algorithm, if the latter can be expanded to solve the same problem it does?’ The difference in approach to the problem is what separates them, to make it simple Dijkstra's algorithm uses a greedy strategy to attain its goal whereas Floyd Warshall's algorithm takes a dynamic programming strategy to solve the same problem.

Note: Difference between Greedy and DP

Both strategies are used to solve optimization problems — which is nothing but a problem where you’re destined to solve for either the maximum or minimum solution possible.

1. Greedy approach: In a greedy algorithm, we make whatever choice seems best at the moment in the hope that it will lead to the global optimal solution.
2. DP: In DP, we make a decision at each step considering the current problem and solution to the previously solved sub-problem to calculate an optimal solution.

Now, it’s all out of the way, let’s jump into the actual algorithm at hand.

Note: Representation of Weighted Graph

Here we’ll be following the adjacency matrix representation of a weighted graph. Where matrix[i, j] is holding the weight of the edge from vertex i to j. For, the absence of self-loop (matrix[i, j], where i = j) it will be 0 whereas if there is no direct edge connecting the vertex i to j then it will be infinity.

Algorithm

So, the formula on which we’re gonna base the decision at each step(as mentioned above it’s the main idea of DP) is that:

A[i,j] = min(A[i,j], A[i,k] + A[k,j])

Okay, first let me break down the formula, A[i, j] represents the edge that is running from vertex i to j, it’s value is the weight on the edge, whereas k is the intermediate vertex which is selected at each step after each update of the matrix. Now, let’s take a look at how the algorithm works:

1. Initially, we have the original adjacency matrix for a weighted matrix.
2. First, we select an intermediate vertex which is going to be known as k.
3. Now, for every element of the adjacency matrix, which A[i, j] we compare the distance to that of the distance which would be if we travel through the intermediate vertex k:

A[i, j] or A[i, k] + A[k, j]

4. We select the optimal distance(here it’s minimum) and update the matrix, by doing this comparison for every element present in the matrix.

5. Now, we repeat the same process by taking every other vertex as the intermediate vertex. (Note: the A[i, j]’s value will be of the updated matrix after the iteration with the previously chosen intermediate vertex k).

Note

If you want to see how the formula is deduced from induction you can refer to the first link in the reference section of this post — Abdul Bari’s DSA youtube channel.

Pseudo-code

Code

Okay now let’s implement the code for the algorithm by taking the below-weighted graph as an example.

Example — weighted graph

The initial adjacency matrix for the above-weighted graph is shown below(please ignore if there are any mistakes with the matrix I have framed the matrix based upon the picture, regardless the code is still correct.)

Adjacency matrix representation for the above graph

The resultant adjacency matrix after running the code:

As you can see from the above image this is the final updated matrix which has the shortest path for every pair of vertices which can be found in the matrix using the Floyd-Warshall algorithm.

Advantages and Disadvantages

Advantages:

1. It works on a weighted graph regardless of the nature of the weights — either positive or negative, unlike Dijkstra’s algorithm which doesn't work on a graph with negative edges.
2. It is easy to modify the algorithm and use it to reconstruct the paths.
3. Versions of the algorithm can be used for finding the longest paths between all pairs of vertices in a weighted graph or transitive closure of a relation R.

Disadvantages:

1. It doesn’t work on a graph with negative cycles.
2. Time complexity: O(N^3), where N represents the number of vertices present in the graph.

So, we have come to the end of this post, and thank you so much 😊 if you’ve made it this far into the post. I will see you in the next post on the Bellman-Ford algorithm! Always grateful, never complacent!

References

1. https://www.youtube.com/watch?v=oNI0rf2P9gE
2. https://www.geeksforgeeks.org/greedy-approach-vs-dynamic-programming/
3. https://www.programiz.com/dsa/floyd-warshall-algorithm
4. https://brainly.in/question/1663295

My Github Repository

1. https://github.com/Sethuram52001/DSA