FLOYD- WARSHAL ALGORITHM
FLOYD WARSHALL ALGORITHM
An algorithm is defined as a set of rules or directions that help us to refine the method for the solution of any problem that needs to be solved or executed in stages. The Floyd-warshall algorithm is the infamous algorithm, used for solving the all-pairs shortest path problem. It computes the shortest distances between every pair of vertices in the given graph. It works for both directed and undirected weighted graphs. This is an extremely simple and efficient algorithm for finding the quickest path among all the other paths leading to the same destination with a direct implementation method.
There are other algorithms like the Bellman-Ford algorithm and Dijkstra’s algorithm for calculating the shortest path in the graph. The limitation with these two algorithms is that they are single-source algorithms, which means that they compute the shortest path only from a single-source.
ALGORITHM-
The Floyd-Warshal algorithm uses the concept of dynamic programming. In dynamic programming, we execute small operations and then simultaneously add them which gives us the final and desired result. In this explanation, let’s take the example of five friends: Akshita, Anamika, Sanya, Nandini, and Rowhi. Now, you know a few routes that connect some of their houses and you know the length of those roads. With the help of this method, we can calculate the optimal route based on the above information. The graph drawn below shows the paths from one friend to another with respective distances.
This will give you the optimal distance between each pair of friends. It will quickly tell the shortest path from Nandini’s house to Rowhi’s house. It has a connecting edge that weights 1. The algorithm will also tell the shortest way to get from Akshita’s house to Anamika’s house is to first go through Sanya’s house, then Nandini’s house, and then Rowhis’s house before ending up at Anamika’s. And hence, it doesn’t matter what house you’re currently in, this method will tell you the fastest way to get to every other house of your choice.
The core working of the algorithm is based on this function,
Sp (i, j, k)
This function returns the shortest path from, A to C using the vertices 1 to k, in the graph shown. The vertices are individually numbered from 1,2,…k.
Now, there exists a base case and a recursive case. Talking about the base case, in this, the shortest path is the weight of the edge connecting A and C:
Sp (i, j, 0) = w (i, j)
Where the shortest path is represented by Sp, and the weight is denoted by w.
In the recursive case, the Floyd-warshal algorithm utilizes the dynamic programming nature of this problem. if we observe, there can be two answers for this function. It’s either the shortest distance from i to j, or it is the shortest known path from i to some other vertex, let’s assume it to be x plus the shortest path from x to j.
Sp (i, j, k) = min (Sp (i, j, k-1)), Sp (i, k, k-1) + Sp (k, j, k-1)
Actually, this entire setup is pointing to the most obvious question which is, “Is the vertex k, the main immediate vertex of our desired shortest path (any other vertex besides the first and the last)?”
Case 1: If k is not an intermediate vertex, then the shortest path from i to j, using the vertices {1, 2, …, k-1} is also the shortest path using the vertices in the set {1, 2, …k}.
Case 2: If k is an immediate vertex, then the distance can be broken down into two paths further, each of which uses the vertices in the set {1, 2, …k-1} to make a path that uses all the vertices in the set {1, 2, …k}. This is all because the vertex k is the middle point. Refer to the diagram drawn below for a proper understanding of the above theory,
PYTHON CODE FOR THE FLOYD-WARSHAL ALGORITHM
Explanation-
The class Edge in line 1 is a simple object that holds information about the edge such as the endpoints and weight. The vertex is merely an integer for this implementation.
The Graph uses a dictionary, which is initialized on line 9, to denote the graph. Keys in this dictionary are the vertex numbers and the values are a list of edges.
Now, the floydwarshall() in line 33, will create a matrix M. it populates this matrix, with the shortest path information from each of the vertex given.
THE TIME AND SPACE COMPLEXITY REQUISITES
The Floyd-warshal algorithm runs in, 0(n³) time. The reason being for the same, that there exists three nested “for” loops that are run after the initialization and population of the path matrix, M.
The space requirements for the Floyd-algorithm to work efficiently are 0(n²). This is because this method completely depends on the number of vertices in the graph.
APPLICATIONS AND GENERALISATIONS
This method can be used to solve a variety of problems,
1. It is the best-suited algorithm for dense graphs.
2. Useful in networking, similar to solving the shortest path problems.
3. It also useful in computing matrix inversions.
4. Maximum bandwidth path in flow networks.
5. Transitive closure of directed graphs.
6. Shortest paths in directed graphs and many more.
7. Surveying distances between the trains is also one of the examples.
In fact, one run of this quick and uncomplicated algorithm can give you all the information you need to know about a static network to optimize most types of paths.
Well, in conclusion, the Floyd-Warshal Algorithm is the most sought-after algorithm whenever there is a case of managing multiple stops on the route because it can calculate the quickest and the shortest paths between all the relevant nodes. This is a highly simple and easy implement algorithm. And obviously, who doesn’t prefer an uncomplicated solution to an already existing complicated situation? Given the popularity and the significance of this algorithm, learning and solving this one is a must-have!
REFERENCES
1. https://brilliant.org/wiki/floyd-warshall-algorithm/
2. https://www.codingninjas.com/blog/2020/09/17/floyd-warshall-algorithm-at-a-glance/
3. https://www.gatevidyalay.com/floyd-warshall-algorithm-shortest-path-algorithm/
