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.