Floyd-Warshall Algorithm and How It Works
INTRODUCTION
Path finding problem is one of the most common problem in computer world. When we travel way far from our home, we use some kind of navigations to give us any information about the streets around us. Another case is when we want to know how many litres of gasoline are enough if we’re going to another town by our car. We’ve been facing path finding problem without even knowing it.
This kind of problem can be solved with many methods. The most commonly used method to solve this problem are Dijkstra Algorithm, A* Algorithm, Breadth First Search, Depth First Search, and many others. Those are the methods we can use to find a path from one point to another. There is also another method we can use to get the minimum cost between all pairs of points we have. The method I’m going to explain is called Floyd-Warshall Algorithm.
ALGORITHM
This method will give us the minimum cost we can achieve between all pairs in the map. In this explanation I’m going to use a graph as the map. Here is the graph we’re going to use.
Here we can see a graph with 4 nodes and 5 edges. Each edge has its own weight, therefore the graph we use is called a weighted graph. The edge that points node number 2 from node number 1 has weight of 4. It means if we want to go to node number 2 from node number one, it’s going to cost us 4.
In the beginning of the algorithm, we will have to create a matrix N x N. N is the number of nodes we have in our graph. Therefore, we have to create a 4x4 matrix in this case.
Each cell in the matrix represents the cost from node i to node j with i is the number of row and j is the number of column. As the initialization, we fill in the cell that has row and column with the same number with 0.
Next, we fill in the cell with the given information in the graph. For example, we can see that there is an edge from node number 3 to node number 4 with weight of 2. Therefore, we fill the cell in third row and fourth column with 2. If a pair does not have an edge between them, we fill the cell with ∞. We do the same way with the others and our matrix is going to be like this
That will be our first matrix. Next step is to fill in all those cell with ∞. We’re going to use iterations with three symbols which is k, i, and j. In each iteration, we have to check the fact if the cost from node i to node j through node k is less than the cost we already have in our matrix. In the first step, we’re going to start each i, j, and k with one.
But, since we don’t need to find the minimum cost from same nodes, we can skip this. The way we are going to find the minimum cost is with this formula.
Cost[i,j] = Cost[i,k] + Cost [k,j]
An example which we can find a minimum cost between two nodes is between node number 1 and node number 4 with k of 2. From the matrix, the cost between those two nodes is going to be ∞ because we haven’t found a path that connects both nodes.
With this, we can find the cost from node number 1 to node number 4 through node number 2 is equal to cost from node number 1 to node number 2 added with cost from node number 2 to node number 4. In this case, the value of i, j, and k will be like this
Therefore, we can get the cost from node number 1 to node number 4 through node number 2, which is 3. Since 3 is less than ∞, we can fill in the cell in the first row and fourth column with 3. This is how our matrix will look like
We continue the same way until k, i, and j are equal to N. At the end of our iteration, we can get the final minimum cost we can get between 2 nodes in every cell we have.
PERFORMANCE
Floyd-Warshall Algorithm doesn’t have a decent performance in a graph with many nodes. The complexity we have is O(N3). This is because the iterations we do when we’re filling the matrix. But, if the graph we’re working on doesn’t have many nodes, it’s still fine to use this method.
One of the advantage we can get by using this method is unlike some other path finding methods, matrix with negative value cost can be used.
APPLICATION
We can use this method in many problems. Surveying distances between train stations is one of them. This method also can be used in listing minimum fuel we need to travel between cities as mentioned above.
In real world cases, we use Floyd-Warshall algorithm to find a regular expression denoting the regular language accepted by a finite automaton by using Kleene’s algorithm which is a closely related generalization of the Floyd-Warshall algorithm. We also use this method to find a maximum bandwith path in network systems.
In the world of mathematics, we can do inversion to a matrix of real numbers. Beside matrix, we can compare two graphs to find the similarities between them.
REFERENCES:
- https://math.mit.edu/~rothvoss/18.304.1PM/Presentations/1-Chandler-18.304lecture1.pdf accessed at 14:34, 21/05/2019
- Chan, Timothy M. (January 2010), “More algorithms for all-pairs shortest paths in weighted graphs”, SIAM Journal on Computing.
- https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html accessed at 19:21, 22/5/2019
