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.