Hello and welcome. My name is William and today we're going to be looking at some source code for the Floyd warshall all pairs shortest path algorithm. Today's source code can be found in the description, but it is also online@github.com slash William slash algorithms. Without further ado, let's dive right in. Here we are in the source code for the Floyd warshall algorithm. So let's get started.

Let's start by looking at an example of how to use this Floyd warshall solver class to actually find all pairs shortest path. So here in the main method, the first thing I do is I actually initialize a graph with n nodes where n is set to seven and I create our adjacency matrix by calling the Create graphs method and if we We look at a peer, this is the Create graph method. And all it does is it initializes a matrix of size n by n, it fills the matrix with the special constant positive infinity. And it also sets the diagonals have all zero nodes by default, because I assume that this is the behavior you want. If it's not, then that's not an issue, because you can just override it when you add some edge values to your adjacency matrix. All right, so we create a matrix, we added some edge weights.

And then what you'll want to do is create an instance of the solver give it our adjacency matrix and then call the get all pair shortest path matrix function which will return the all pair shortest path matrix as a matrix called just for distance. And then here all I do is I loop over all pairs of nodes. iMj and I print with the shortest path from node i to j is, here's a sample output of what that looks like. So there can be roughly three different kinds of outcomes, we get a concrete shortest path, there does not exist the path between the two nodes, that'd be infinity, and we encounter a negative cycle, so that is negative infinity. Similarly, if we want to reconstruct the paths, this is how we're going to do it. Don't be scared by any of this.

It's just text being printed on the screen. So here I want to reconstruct the shortest path between all pairs of nodes. So I loop through all pairs of nodes i and j. And then on the solver, again, I call reconstruct shortest path from i to j, and that returns a list of nodes. And here I just print three different options depending on when I get back if the path is Then there does not exist. Or rather sorry, there exists an infinite number of solutions.

If the path has zero length, there is no solution. And otherwise I just do a pretty formatting of the output. And this is what that would look like. So just prints what the path would be between all pairs of nodes. So for instance, the shortest path from node to node zero to node two and our graph goes through nodes 01 and two, and it does, it just prints all this information for all nodes in our graph, which is really useful. Okay, so what is this?

Floyd warshall solver actually doing and that's what we're going to look at right now. So inside that class, we have for instance variables, and the number of nodes in our adjacency matrix, a boolean value called solve which is Just tracks whether we've solved the all pair shortest path problem or not our dp matrix and a next matrix, which is used to reconstruct the paths. And there's also this constant, which I just initialize to minus one so we can identify when we've reached negative cycles. Okay, so looking at the constructor, again, you just pass in the input adjacency matrix, and then I do some initialization. So simply allocate memory for our matrices that we're going to need, and then populate the DP matrix with whatever is given to us for our input. And also make sure to initialize the next matrix to contain j as the next value going from i to j.

And that's all you need to do. For the setup, nothing too complicated. Let's look at some of the methods that are provided in this class. The first one is get all pair shortest path matrix, which is the first method we called. And what that does is it looks if we've solved the all pair shortest path problem already, and if not a cause the solver. The reason I do this is so that if we want to get the old pair source path matrix multiple times that we don't run the solve method several times.

So the solve method is what actually solves or rather executes the Floyd warshall algorithm. And here's what we're going to do to compute all pairs of shorts paths. First, we iterate through k on the exterior loop, and then we loop through all pairs of nodes and then we check for our condition. So if the path is Going from itk and then k back to j is less than the path from i to j, then update the value of it j to route through that node k. And while doing this also update the next matrix so that we can reconstruct the path later on. So it is now shorter to go through it Okay, then it j so update the indices for a hijack. This next loop is if you want to identify negative cycles, identifying negative cycles means that we need to propagate the value of negative infinity throughout our graph for every part of the graph that reaches a negative cycle.

So, basically if we can improve upon the already optimal solution, then we know that we're reaching a negative cycle somehow that that particular edge is compromised, so simply mark it with negative infinity. That is again one of the special constants provided by Java. Similarly, update the next matrix to also mark the node as being contended by negative cycle. But since next stores integer values, we can't give it the value negative infinity which is a double. So give it the value minus one stored in reaches a negative cycle. And once that is done, we have fully executed the Floyd warshall algorithm.

And we can mark our boolean value of solved as true. Now if we look at reconstructing the shortest path, from the start node to some ending node, what we want to do is if we haven't done so already, run the solver and then initialize a value called path to an empty ArrayList. Look at if it's even possible to reach the end node from the start node. And if it's not return an empty path. Otherwise populate the path with the current node, which I noted, denoted as x. And for each current node, check if we reach into a negative cycle.

And if we do return No, because the best value, or sorry, the shortest path doesn't exist, because there are an infinite number of shortest paths. And also make sure to check the edge case where the last note is part of an infinite loop and simply return the shortest path. So guys, that's about it for the Floyd warshall algorithm source code. If you have any questions, just drop a comment in the description and I'll get back to you as soon as I can. Guys thanks for watching. Please subscribe for more mathematics.

And computer science videos. Thank you