So related to the topic of topological orderings is the topic of shortest and longest paths on directed a cyclic graphs. Recall that a directed acyclic graph is a graph with directed edges and no cycles. By definition, this means that all trees are automatically directed acyclic graphs, since they do not contain any cycles. Here is a graph. My question to you is, is this graph a directed acyclic graph? And the answer is yes.

But what about this structure? I'll give you a moment to think about it. The answer is no because this graph has undirected edges as opposed to directed edges. The graph that may be a tree, but directed edges are a record acquirement for a directed acyclic graph. What's really great about working with directed acyclic graphs is that the single source shortest path problem can be solved very efficiently. In fact, in linear time, the next fastest single source shortest path algorithm is textures algorithm, which may not work if there are negative edge weights.

This algorithm I'm about to show you is faster and doesn't care about positive or negative edge weights. The essence of the algorithm is that it finds a topological ordering on the graph using the top sort algorithm we saw in the last video and processes each node sequentially to get the shortest path by relaxing each edge as it is seen. Relaxing edge simply means updating to a better value if the shorter path be obtained using the current edge. Suppose this is the graph we're working with, you can verify that it is in fact a directed acyclic graph. What we wish to do is find the shortest path from node A to all other nodes in the graph. In order to do this, the first thing we'll want to do is generate a topological ordering of the nodes of this graph using the top sort algorithm.

Below, I have selected an arbitrary topological ordering, which is the order we will process the nodes in this graph. I'm also displaying the current best distance to each node at the bottom of the screen, which are all currently set to infinity. The first step of the algorithm is to set the distance to the starting node to be zero. In this case, since a is the starting node, its initial distance to zero because we're already there, from a want to visit all reachable nodes starting with node B, and update the value to B, if it is better than what was already there. This is the edge relaxation step of the algorithm, we noticed that a value of three is better than infinity. So we update the best value of b to be three, then the best value to C to be six.

And now we've explored all of his edges and want to move on to the next node are topological ordering which is B and explore all of its edges. So the first edge brings us to node E and we update its best value to 14 because the best value at node B was three plus the edge weight to get e was 11 for a total of 14. Notice that at Get grayed out as they're being processed. Next, we update the best value to D to B seven. Now, we've reached the first instance where it is best not to update the value of the destination node, since a better path already exists to where we want to update. Now we move on to the next node or topological ordering and keep repeating the same steps where we explore all the nodes.

Try and relax each edge and then move on to the next node and the topological ordering. If we repeatedly do this, the rest of the bottom the screen will contain the shortest path from node A to each node. I will let the animation play and you can try and determine the shortest path to all the remaining nodes which have not yet been processed. Okay, we're done processing all the nodes and know the shortest distance to every note, let's verify our algorithm computed the correct values by finding the shortest path to node H. Indeed, if we look at the path and some of the values along the edges, you will find that they do indeed sum up to 11, which is the shortest path in our array for node H. There's a similar problem to the shortest path problem, which is finding the longest path in the graph.

This problem is actually NP hard on general graphs, but can actually be solved in linear time on a directed acyclic graph. The trick is going to be to multiply each edge by minus one, find the shortest path, and then multiply all the edge values by minus one again. Take the previous graph, we had to find the longest path, simply negate all the edges, then find the shortest path and multiply the answer by minus one. And there you go. That's all you need to do. Okay, and now let's have a look at some source code.

You can find the code I'm about to show you on github@github.com slash Wm is that slash algorithms. Here I am on GitHub, and we're looking at some code for the shortest path on a directed acyclic graph. Here's our method directed acyclic graph shortest path And it returns the distance to each node sorted in integer array for some starting node, and as input we give it the graph or working with as an adjacency list, of course, the starting node and lastly the number of nodes in our graph. So what we do is find the topological ordering for our nodes. I covered this in the last video, then initialize our distance array and then set the story nodes distance to be zero. And all we do is we loop through each node starting at the first node, looking at what our node index is for top sort, so this is the first node we need to visit and then check if that node is not equal to new All, and then grab all the edges for that node.

So we reach in our graph and then pull out all the edges for the node index. Make sure there actually are some edges. And then for each edge in the edges that we got, which were the adjacent edges, then all we do is the relaxation step, which is just this. So we compute the new distance. So this is the distance to the node. We're currently at plus the edge weight.

So this is like the competing distance, the distance we were trying to improve upon, then we check, okay, has there ever been a distance set to where we want to go? This is basically the equivalent of infinity. And if so then we just want to give the new distance otherwise, we're going to take the minimum of the distance that's already there. And our new competing distance, which is this over here. And then we just do this over and over again, processing nodes and topological order because we're pulling them out of the top sort array. And at the end, we just return that distance array.

And we can get the distance from our starting node to any other node in the graph, just through a lookup and this array. And guys, this is super simple algorithm. And that's all there is to shortest paths on directed acyclic graphs. Thank you for watching. Please like this video and subscribe to my channel for more Computer Science and Mathematics videos. Thank you