0:00

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.

Â 2:36

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.

Â 7:27

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.

Â 9:40

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.

Â