In this next sequence of videos, we're going to revisit the single source shortest path problem. This is a problem that we already solved using Dijkstra's greedy algorithm. Now let's see what the dynamic programming paradigm can do for us for the same problem. Let me just quickly remind you the definition of the problem, what's the input, what's the output. We're given a graph. And when we talk about shortest path, we're going to be discussing only directed graphs. Each edge of the graph has a length, which we're going to denote by c-sub-e. And one vertex which we'll denote by a little less is designated as the source vertex. We're going to assume that the graphs are simple. That is, there are no parallel edges. The reasoning is the same as the minimum spanning tree problem if you had a bunch of parallel edges. Since we only care about the shortest path, you may as well throw away all of the copies of an edge except for the one that has the smallest length. The responsibility of an algorithm for this problem is to compute the length of a shortest path from this source vertex S to every other possible destination V. And always, when we talk about the link of a path, we mean the sum of the edge costs, of all of the edges that are in that path. For example, if the cost of every edge was one, then we'd just be talking about the hob count, and that's a problem that's solved using breath per search. But in general in this single source shortest path problem, we're interested in edges, that has possibly wildly different links from each other. So let's now review our existing solution for the problem Dijkstra's algorithm. Review its pros and its cons. The Dijkstra's algorithm is a great algorithm. If you have a graph and it fits in your computer's main memory and all the edge costs are non negative, if you implement Dijkstra's algorithm using heaps, you will get a blazingly fast and always correct shortest path algorithm. Part one of this course we explained an implementation using heaps that runs in Big O of M times login time. Where as usual M is the number edges and N is the number of vertices. And this implementation is almost identical to the one we discussed earlier in this course for prims algorithm computing the minimum of a spanning tree. It turns out you can get an even better acetonic running time, at least theoretically, a running time of M. Plus and login if you use a more exotic type of data structure but let's for now just think of this as the line in the sand big o of m login using dice wishin algorithm on a graph with non negative edge lengths. So given what a great algorithm Dijkstra's algorithm is, on what basis could we reject it and study any other shortest path algorithm? Well, there's two drawbacks we've mentioned before, let me reiterate them now. So first of all if you're working with a graph where some of the edge costs can be negative, then the output of Dijkstra's algorithm need not be correct. The correctness relies on the non-negative edge cost assumption. We saw concrete examples of this both back in part one of the course, but also in this course when we first started talking about greedy algorithms and we discussed to their ubiquitous incorrectness. Now frankly, for many of the applications of shortest path algorithms you're never going to run into negative edge lengths. If you are implementing, for example, a program that computes driving directions, whether you're doing it in miles or in time, you're not going to have negative length edges, at least until we get finally get around to inventing those time travel machines. But not all applications of the shortest path problem are so literal and involve literally computing some path in space from some point A to some point B. More abstractly, the problem is just helping you find an optimal sequence of decisions. Imagine you were managing a bunch of financial assets, for example, and you were modeling a single transaction as an edge in a network that takes you from one particular inventory to another. When you sell stuff, that might generate positive revenue and correspond to a positive edge length, but when you buy stuff then, of course, you have to spend money and that can correspond to a negative edge length. So the second drawback which we mentioned in the intro video for this course, is that dijkstra's algorithm seems highly centralized. Now, that's not a problem if you just are destroying the entire graph in the main memory of one machine, but if you're talking about routing in the interenet. Well it's totally impractical for a router to have a up to date complete map of the entire internet to compute routes locally and so that motivates looking at a different shortest path algorithm, which is better suited for distributed routing. So we're going to be able to address both of these drawbacks in one fell swoop via the Bellman-Ford algorithm, which will be yet another instantiation of the dynamic programing algorithm design paradigm. This Bellman Ford algorithm, despite predating the earliest version of the ARPAnet by a good ten years, nevertheless does form the basis for modern day internet routing protocols. Of course there's a lot of engineering steps that you need to go from the abstract Bellman Ford algorithm to practical solution internet routing. We'll discuss that a little bit in a separate video, but this really is where it all gets started. So before we start developing the Bellman Ford algorithm, we need to take care of some subtle preliminaries. We need to be clear about how we're defining shortest paths in the presence of negative edge costs and in particular in the presence of negative edge, negative cost cycles, that is a directed cycle of edges where the sum of the edge costs is less than zero. You can think for example about this green cartoon I've drawn off on the right where somewhere embedded in this graph is a directed cycle that has four edges. Some of the edges in the cycle have negative cost, some have positive but on balance the cycle has negative overall cost, cost minus two if you traverse all four of the edges. So let's think about how we should define the shortest path from the source vertex S to some destination V in a graph like this. Do, in particular, do we allow cycles in the path or not. So first let's think through the ramifications of allowing the paths to include cycles. So this proposal actually doesn't make sense. In that generally there will be no shortest path from S to V if you allow cycle traversals. The reason being that if you have a negative cycle like this one of overall cost minus two in the screen graph, and you can actually reach it from the source S, then for every path you can actually find another path which is even shorter. You traverse the directed cycle one more time. The path overall path link drops by another minus two, and there's nothing from stopping you from doing this over and over and over again. So either the shortest path you can think of it as being undefined. Or you can think of it as being sort of, minus infinity in the limit. So if permitting our path to have cycles didn't work, why not we explore the option where we forbid cycles in our paths? So this version of the problem is perfectly well defined. It's a totally sensible computational problem, which you might well want to solve. The issue here is much more subtle. The issue is that this problem is what's called np complete, so that's something we'll discuss much more next week. But the bottom line is these are intractable problems. There are no known computational efficient, no known polynomial-time algorithms for np complete problems. And this, unfortunately, is one such problem. Computing shortest cycle-through paths in the presence of negative cycles. So a bit more precisely, if you came up with a guaranteed correct and guaranteed polynomial time algorithm, that was computed shortest path and presence of negative cycles, the, a consequence would be what's called P = NP. And that's something we'll discuss a bit more formally in a later video. But, certainly if you came up with such an algorithm you should report immediately to the Clay Institute. They would have a $1,000,000 prize awaiting for you for such an algorithm. So for those of you that are already familiar with NP completeness, it would be an easy exercise to prove that this problem is NP hard. It would just be a reduction from the Hamiltonian path problem. So it seems that we are stuck between a rock and a hard place. If we allow cycles in our paths, we don't get a meaningful problem. We get something that doesn't make sense. If we exclude cycles, we get a perfectly meaningful, but unfortunately computationally intractable problem. So here's how we're going to proceed, we're going to focus for now, just on graphs that do not have negative cycles. We will of course allow individual edges to be negative, but we're going to insist for the moment that every single directive cycle of the input graph has overall non negative length. So we can have some positive edge cost, some negative edge costs. But overall it has to be non negative. Now I don't blame you if this assumption bothers you, but the good news is, as we'll see, the Bellman-Ford Algorithm effortlessly checks whether or not this condition holds. It effortlessly detects a negative cycle in the input graph if one exists. So the version of the shortest path problem that Bellman Ford Algorithm is going to solve will be the following. Given an input graph which has. Negative edge costs. It may or may not have a negative cycle. The Bellman Ford algorithm will either correctly compute shortest paths from the source to all of the destinations just like you wanted, or it will punt, but it will offer you a good excuse for why it punted. It will show you a negative cycle in the input graph and of course computing shortest path is intractable in the presence of a negative cycle so with Bellman Ford you have to sort of let it off the hook in that case. Okay? So it will give it an input graph either it will show you a negative cycle or it will give you all of the shortest path distances. That's the guarantee we're going to strive for. So I'm going to end this video with a quiz helping you understand why this hypothesis of no negative cycles might be useful in an algorithm. So for now I just want you to think about suppose I promised you that an input graph had no negative cycles. And the question is how many hops, how many edges, are sufficient to guarantee that you found the shortest path between S and some given destination phi. So the correct answer is A and this is one of the main reasons the no negative cycle hypothesis is useful it gives you control over how many edges are necessary to ensure that you've got the shortest path. So specifically suppose you had a path between some S and some V that had at least. N edges. Well if we have at least ten edges it means the path visits at least, N+11 vertices. There's only N vertices, so if you visit at least, N+11, that means you visit one vertex twice, say X. So, that means you have a cycle inside your path that goes from X back to X again. Now, if you rip out this cycle, if you just delete those edges you get another path from S to V and because, this directed cycle as they all are, must be non negative. The total length of some of the edge cost has only gone down, by removing this cycle, so you show me, Path from s to the u with the least end edges I will show you a path with fewer edges and that is at least as short could only be short so that shows you that the shortest path or a shortest path has our most n minus one edges which is the answer to the quiz.