Hello and welcome. My name is William and today's topic is the Floyd warshall all pairs shortest path algorithm, we will be covering how the algorithm works, how to reconstruct shortest paths, the handling of negative cycles followed by some code. So let's get started. In graph theory, the Floyd warshall algorithm is an all pairs shortest path algorithm. This means it can find the shortest path between all pairs of nodes. This is very important for many applications across several fields.

The time complexity to run Floyd warshall is big O of V cubed, V being the number of vertices in the graph. This makes the algorithm ideal for graphs with no more than a couple hundred nodes. Before we dive too deeply into the Floyd warshall algorithm, I want to address when you should and should not use this algorithm. This table gives information about various types of graphs and or constraints in the leftmost column, and the performance or outcome of common shortest path algorithms. For example, you can see in the second row that a breadth first search, and Dykstra is can handle large graphs with lots of notes, while Bellman Ford and Ford warshall not so much. I suggest you pause the video and really go through this table and make sure you understand why each cell has the value it does.

What I want to highlight is the rightmost column since we're talking about the Floyd warshall algorithm, the Floyd warshall algorithm really shines in three places, and those are on small graphs, solving the all pair shortest path problem and detecting negative cycles. You can use the algorithm for other tasks, but there are likely better algorithms out there with Floyd warshall. The optimal way to represent our graph is with a two dimensional object. Since the matrix, which I will denote as the letter M, the cell m ij represents the edge weight of going from node i to node j. So in the image below, I transform the graph with nodes ABC and D into an adjacency matrix on the right. An important note I should mention is that I assumed that the distance from a note to itself is zero, which is usually the case.

This is why the diagonal has all zero values. When there is no edge between nodes i and j, set the value in the matrix some m ij to be positive infinity. This indicates that two nodes are not directly connected to each other. A very important note to make is that if your programming language doesn't support a special constant in its standard library for positive infinity, such that infinity plus infinity equals infinity and infinity plus x equals infinity, then you should avoid using two to the power of 31 minus one as infinity. If you do so, then you will likely get integer overflow simply use a large constant instead, as we will see the main idea behind the Floyd warshall algorithm builds off the notion that you want to compute all intermediate routes between two nodes to find the optimal path. Suppose, our adjacency matrix tells us the distance from a node A to a node B is a letter.

Now, suppose there exists a third node C, if the distance from A to C and then C to B is less than distance from A to B, then it is better to go through node C. Again, the goal is to consider all possible Intermediate paths between triplets of nodes. This means we can have something like this, where the optimal path from A to B is first going to C, then going from C to B, but in the process, we actually route through another node, which I labeled with a question mark. Because we've already computed the optimal path from C to B and another involves an intermediate node. Similarly, we can get longer paths with more intermediate nodes between A and C and C and B with the smart cast. We are also not just limited to one intermediate node in between A and C, and C and B, we can have several like in the graph below.

Now the question comes up how do we actually compute all intermediate paths? The answer is we will use dynamic programming to cache previous optimal solutions. Let dp be a three dimensional matrix of size n by n by n, which acts as our memo table, we're going to say that the cell dp at K IJ in our table gives us the shortest path from node i to node j, routing through nodes zero through K. What we'll do is starts by computing k equals zero, then k equals 1000, k equals two and so on. This gradually builds up the optimal solution routing through zero, then all optimal solutions, routing through zero and one, then all optimal solutions routing through 01 and two, and etc. Up until we covered all nodes, at which point we have solved the shortest path problem. Let's talk a bit more about how to populate the DP table.

In the beginning the optimal solution from i to j is simply Distance given to us in the adjacency matrix. So when k equals zero, dp of K ij is equal to m ij the value of the edge from i to j. Otherwise, in general dp, k ij can be summed up with the following recurrence relation. I'm going to break it down so that we can understand all its components because this may look scary to some people. The left hand side of the recurrence simply says, reuse the best distance so far from itj. routing through nodes, zero to k minus one.

It's important to note that the solution using nodes zero to k minus one is a partial solution. It is not the whole picture. This is part of the dynamic programming aspect of the Floyd warshall algorithm. The right hand side of the recurrence finds the best distance from i to j. Bo routing through node k, reusing the best solutions from zero to k minus one. If we analyze the right side of the main function in English, it basically says go from i to k, then go from k to J. Visually, this is what it looks like. You start at I route through some nodes to get to k, and then from K route back to J.

Currently, our algorithm uses big O of V cube to memory. Since our memory table dp has one dimension for each of k, i and j. This isn't particularly great. Notice that we will be looping over k starting from zero, then one, then two, and so forth. The important thing to note here is that previous results build off the last since we need the state of k minus one to complete state k. That being said, it is possible to compute the solution for K in place, saving us a dimension of memory and reducing the space complexity to big O of v squared. Now we have a new recurrence relation which no longer involves the Cade I mentioned, this has been replaced by the fact that we're computing the k plus one solution in place inside our matrix.

Okay, that's all the theory we need. For now, let's get our hands dirty and look at some pseudocode. Below is the function that actually solves the Floyd warshall algorithm or rather executes the Floyd warshall algorithm. But before we get into that, let's look at some of the variables I have defined in the global or class scope, which I will be using throughout these functions. The first variable is the number of nodes in our graph. Then is the 2d memo table that will contain our all pair shortest path solution.

Last is the next to the table that we will use to reconstruct our shortest paths. Now moving on to the Floyd warshall function, you see that it takes one parameter. This is the 2d adjacency matrix representing our graph. The first thing I do in the method is call the setup function. So let's take a look at that real quick. So here we are inside the setup function, the first thing I do is I allocate memory for our tables, the DP matrix should have the same type as the input adjacency matrix.

What I mean by this is if your edges in your input matrix are represented as real numbers, then your dp matrix should also hold real numbers. The next matrix will contain indexes of nodes to reconstruct the shortest paths found from running the Floyd warshall algorithm. It is important that initially this matrix be populated with null values inside the for loops, all I do is copy the input matrix into the DP matrix. Think of this as the base case or rather the K equals zero case. For the next matrix if the distance from i to j is not positive infinity, then the next node you want to go to from node i is node j by default. Now we're back inside the Floyd warshall function.

In here after the setup, loop over k on the exterior loop, it's important that k is on the exterior loop. Since we want to gradually build up the best solutions for k equals zero, then k equals 1000 k equals two and so on. Followed by this loop over all pairs of nodes i and j. Inside the main body actually tests for our condition to improve the shortest path from J going through K and update the value at dp ij. If there is a better route through K, also inside here Okay, the next array at ij to point to the next index. Next ik.

The last thing I want to do is to detect and propagate negative cycles. This is an optional step if you know that negative cycles will not manifest themselves within your graph, although I still recommend you keep this function around. But before we get too far, I want to discuss negative cycles and what they entail because it isn't entirely obvious. So consider the following graph. There are basically two types of nodes to consider here. Nodes directly involved in negative cycles and nodes unaffected by negative cycles.

This red node is the cause of a negative cycle because it Can endlessly loop on itself and obtain smaller and smaller costs. While these blue nodes are not directly in a negative cycle. This however, doesn't mean they're not necessarily safe from negative cycles. As we will see, negative cycles can also manifest themselves as groups of nodes working together like the following. So an important thing to ask ourselves is does the optimal path from node i to node j go through a red node, if so, the path is affected by the negative cycle and is compromised. For example, the shortest path from zero to five is negative infinity.

Because I can go from zero to node two and indefinitely loop in the negative cycle consisting of nodes, one, two and three obtaining better and better costs before eventually going to find This is a consequence of traversing a red node on the way to five. Some shortest paths. However, avoid red nodes altogether, consider the shortest path from four to six. This doesn't involve any red nodes, so we can safely conclude that the shortest path from four to six is indeed two. So to identify whether or not the optimal path from i to j is affected by a negative cycle, rerun the Floyd warshall algorithm second time, if the best distance is better than the already known best distance stored in our table dp, then set the value in the matrix from i to j to be negative infinity also mark the index at ij in the next matrix with a minus one to indicate that the path is affected by a negative cycle.

We will use this shortly. Can Floyd warshall function all we need to do is return the matrix dp, which contains the shortest distance from any node to any other node. This is the solution to the all pairs shortest path problem. The last thing I want to cover is how to reconstruct the shortest path between any two pairs of notes. This method returns the shortest path between the start and end nodes specified or no if there is a negative cycle, first check the distance between the start and end nodes is positive infinity. If so then return an empty path.

Then to reconstruct the path I create a variable called act to track the current node, and then I loop through the next array, adding the current node to the path as I go. During this process, I check if the current node has the value minus one. If it does, then this means that the optimal path encountered a red node and is trapped in a negative cycle. So return now notice that in reality, this method has three key return values, an empty path, which means that the start and end nodes are not connected a null value meaning a negative cycle was encountered. And lastly, a non empty path of node indices to mean an actual shortest path was found. So I think that's about everything you need to know about the Floyd warshall algorithm.

The next video I'm covering real source code for this, so stick around for that. You can also get access to the real source code@github.com slash Williams slash algorithms. There should also be a link in the description. Thanks for watching and sticking around. Please subscribe for more mathematics and computer science videos.