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.