- [Instructor] So in an earlier video,
we saw Dijkstra's algorithm.
We saw how we can take a graph, weighted edges
and find the shortest path
from some node to all the other nodes in the graph.
And that's great.
And that worked as long as we didn't have
any negative edge weights.
When we talk about the shortest path,
we really should be talking about the lowest cost path.
And it turns out that there are a lot of applications
where we may have positive and negative weights
that don't necessarily refer to distances.
We talk about the shortest path in a graph,
but the actual real world problem that we're modeling
might be measured in dollars or in calories.
We have a graph here on the left
that has some negative weights.
We have negative three, negative two,
and we've learned that Dijkstra's algorithm doesn't work.
It gets grumpy, and it doesn't work
if we have negative weights.
But as I'm hinting, there are many applications
where negative edge weights are useful.
I'll give you a couple of common examples.
One example is currency arbitrage
where we have different exchange rates between currencies
and you can represent these costs of changing currencies
with a graph and you can identify
what are called arbitrage opportunities
by finding lowest cost paths that optimize your profit.
Another example is a chemical reaction
or a chain of chemical reactions.
As you may know, some chemical reactions consume energy
and some chemical reactions give off energy.
And so we might be interested in finding the series
of chemical reactions that yields the lowest cost
or that releases the highest amount of energy.
And so we can model our chemical reactions
where we have positive and negative weights
depending on whether the chemical reaction
consumes energy or releases energy.
So those are two common examples.
I'm gonna give you another.
So in keeping with our earlier discussions
of roots and cities, what's shown here aren't distances,
but are costs.
So let's say we have a truck, we've got a truck.
Here's our truck.
Our truck is in Albuquerque, New Mexico
and we want to get home to Fresno, California
with as much money in our pocket as possible.
So the cost of driving the truck is about 42 cents a mile.
We get about seven miles to the gallon.
We got diesels about three bucks a gallon
so call it 42 cents.
But at certain points,
we can pick up goods and deliver them.
I mean, that's the point of having a truck.
So here from Flagstaff to Phoenix,
we can pick up something in Flagstaff
and deliver it to Phoenix and we turn a profit, 70 bucks.
So we represent that as a negative number.
Here, we just have a cost.
This is the cost of our fuel
driving from Albuquerque to Flagstaff.
There's nothing that we can carry
from Albuquerque to Flagstaff to offset that cost.
In some cases, the cost is offset partly,
but in some cases we actually turn a profit.
Again, here's another path with a profit
where we take some say farm goods from Bakersfield
to Los Angeles.
And so we've got all these cities, we've got all these costs
and we want to find the lowest cost path
from Albuquerque to Fresno.
Does that go through Flagstaff and Bakersfield
or does it go through Las Cruces and Tucson?
It looks like we have a high profit trip here
from Tijuana to San Diego,
but it's not immediately evident
what the lowest cost path is.
So what do we do?
We've already seen that Dijkstra's algorithm won't work.
So what can be done?
We use the Bellman-Ford algorithm.
Now we saw earlier that there was the catch,
there's always a catch.
So Dijkstra's algorithm is great.
It has this relatively low worse case complexity,
but we can't work with edge weight that are negative.
If we have a negative edge weight, we're no good.
So we need another solution and we have Bellman-Ford.
Bellman-Ford is a more costly algorithm to run
instead of big O of the cardinality V
plus the cardinality V times the log
of the cardinality of V.
We have a big O of the cardinality V
times the cardinality of E
and we'll see that we have a nested loop in there.
So it's more expensive.
So if we know we have all positive
or I should say all non-negative edge weights,
we should use Dijkstra,
but if we have negative edge weights,
we should use Bellman-Ford,
but there's a restriction for Bellman-Ford too
and that is that there must be no negative cycles.
So that's another restriction here.
So we have to think about what is a negative cycle.
And then once we figure out what a negative cycle is,
I'll walk you through an example of Bellman-Ford.
Here, we've got this directed cyclical graph,
and you can see we have a cycle here.
We have a cycle here.
Now, what is a negative cycle?
Well, this is a counter example.
This is not a negative cycle.
We have edge weights of one plus three minus two
gives us a sum of the edge weights is two
and that's not negative so that's not a negative cycle.
Let's look at this one over here.
We've got one plus two minus three is zero plus seven
so the sum of the edge weights here is seven
and that also is not a negative cycle.
But here we do have a negative cycle.
We have edge weights of three plus two is five minus seven.
This is negative two.
Now, why is this a problem?
Well, if I want to get from one place to another
with the lowest cost, say I wanted to get from A to H,
I could continually reduce my cost
by traveling in this loop.
Every time I go through this loop,
I'm gonna reduce my cost by two.
Negative two, negative four, negative six, negative eight
so I'm gonna start here.
I've got six.
I go around once, I got four, I go around once, I got two,
I go around once, I got zero, I got negative
and there's no end to it.
So this is not a way to find the lowest cost path,
it's gonna lead us to infinite regress.
So that's why we can't have negative cycles
in a graph and use Bellman-Ford.
So what does the Bellman-Ford algorithm look like?
Well, it looks an awful lot like Dijkstra.
Some of the code here is absolutely identical.
So we have this function, Bellman-Ford, just like Dijkstra,
it takes in a graph and a starting node S.
And then the initialization, this part of the code here
is absolutely identical.
For each node in the graph, we set the arrived from
for that node to be null at the starting point.
If the node is the starting node,
we set the distance to zero.
Otherwise, we set it to infinite.
Again, identical to Dijkstra.
Now here we have a little difference,
but before I explain the difference,
I'm gonna draw your attention
to these four lines of code or pseudocode I should say.
And these again are absolutely identical to Dijkstra.
We calculate the distance
which is the distance we've already found
plus the weight of the edge to the new destination.
And if the distance is less than that
of the current value for the destination,
then we know we found a shorter distance
and we do this update where we update the distance
and we update the arrived from.
These four lines of code are identical to Dijkstra.
So what's different?
What's different is that rather than a while loop,
we have to repeat a fixed number of times
or we do have some early termination conditions.
So in the worst case,
we have to repeat the cardinality of V minus one time.
So if you have a graph on six nodes,
we have to repeat this outer loop five times.
If we have a graph of 100 nodes,
we have to repeat this loop 99 times.
And then there's an inner loop
and we have to iterate through all the edges
in the graph for each iteration of the outer loop.
So this is cardinality of V.
This is cardinality of E
and that's where we get the complexity
big O of cardinality of V times the cardinality V
because we have this invested loop,
outer loop is V, inner loop is E.
We also have this check here at the end,
the very end we've executed the algorithm.
We do this check to see
if there are negative cycles in the graph
and we have to go through all of this stuff first
before we can do our check.
For each edge in the graph going from U to V,
we check to see if the distance to V is greater
than the distance to U plus the weight of that edge.
And if it is, we know we found a negative cycle
and I'll give a demonstration
of why that works a little later,
but now let's go through an example of Bellman-Ford.
So here we have this directed cyclic graph.
Do we have cycles here?
Yeah, we do.
So this is a directed cyclical graph,
but it has no negative weight cycles
so we have this cycle here from B to F to D to B again,
but what's the sum here is one.
So this is negative five, but the cycle weight is one.
So we're good there.
We also have this cycle here, two, two, five,
but those are all positive
so that presents no problem for us.
And I've initialized this graph,
the starting node here as weight zero,
all the others have infinity,
just like we would do with Dijkstra
and noticed that we have six nodes
so we would have to execute in the worst case five times.
And over here, this is just a list
of all of the edges in the graph.
So remember at each iteration,
we're gonna have to check this edge
and then this edge and then this edge
and then this edge and then this edge.
So I've got this over here just so we can keep track
of the edges that we've checked so far, just visually.
So on our first iteration, we first check edge AB
and we find a route from A to B,
path from A to B of weight seven.
And so we update the value for B to seven
and indicate that we got there from A,
then we check AF.
What happens with AF?
We've discovered a path F of weight six
and we got there from A.
Now we check BF.
From B to F, we have a weight of seven plus four is 11.
11 is not less than six so we don't update here.
Now we do from B to C
and we've discovered a new shortest path of weight 13
so we make a note of that here, that we arrived from B.
Now we check from D to B, but D to B, D is infinite
and so this is gonna give us infinity minus five,
which is certainly greater than seven
and so we don't do an update.
And then we do D to C, same thing,
infinity minus three, no update.
Infinity plus two is not less than infinity
so we don't do an update there.
And now we check from F to D and we find a path to D
that goes from A to F to D and it has weight eight
and so we make a note that we arrived at D from F.
So there's a new shortest path that we've discovered.
Then we check H to C and we have the same infinity case
so there's no update.
And H to F again, no update.
So that concludes our first iteration.
Now we do our second iteration.
From A to B, there's no change.
From A to F, no change.
From A to B...
I'm sorry, from B to F, that's this one here.
No change, because again, 11 is still greater than six.
We checked it last time, still no change.
From B to C, no change.
From D to B, now we have a change.
We had a weight of seven.
Now we have a weight of three, why?
Because now we found this new shortest path
that goes through D so six plus two minus five is three
and so we arrived at B with this new shortest path from D.
Now we check from D to C and we get an update there.
The old was 13, now it's five
because now we have this shortest path,
six plus two minus three is five
and that's our new shortest path to C from D.
Now we check D to H and we get a new shortest path here.
We had infinity, now it's 10 because D is eight
plus two is 10.
Now from F to D, F to D, we've got no change here.
And we check H to see.
10 plus five is 15 is greater than six so no update.
And H to F...
I'm sorry, I should have checked this one here.
That was 10 plus one is greater than five so no update
and now 10 plus five is 15 is greater than six so no update.
And that concludes our second iteration.
Now I've contrived this example
so that we have no updates in the third iteration.
So you'll see what early termination looks like.
And so we check AB, no change.
AF, no change.
BF, no change, BC, no change.
D to B, no change.
D to C, no change and so on through the rest of the graph.
And so we've made an iteration without any updates
and therefore we know that any subsequent iterations
will also have no updates so we can terminate early.
So we're done with this part of the algorithm
and now we check for negative cycles.
And if you'll recall,
the way we checked for negative cycles is we check to see
is the distance to B here
greater than the distance from this node
plus the edge weight.
And no, three is not greater than zero plus seven.
We check this one, six is not greater than zero plus six
so we're good there.
B to F, we have three plus four is seven.
Six is not greater than seven, so we're good there.
B to C, five is not greater than three plus six
so we're good there.
D to B is eight minus five.
Three is not greater than eight minus five
so we're good there
and so on throughout the rest of the graph.
So all of these edges pass that test.
And so we have no negative cycles and we're done.
And as before with Dijkstra,
we can reconstruct any shortest path
by following these pointers.
So for example, the path from B,
we go backwards to D.
From D, we go backwards to F.
From F, we go backwards to A, and so we know
that this shortest path to B, which is of weight three
is this path from A to F to D to B, and we can do this
for any node in the graph,
find its way back to A.
So that's again just like Dijkstra's.
So why do we need up to V minus one iterations?
Well, if we have the cardinality of V nodes,
then the shortest path can have no more
than the cardinality of V minus one edges.
And when we iterate at the case iteration,
we know we've covered all the shortest paths up to length K,
now we need to consider all the shortest paths
so we need K to equal the cardinality of V minus one.
So at each iteration, we may add more and more length
to some of these paths
and therefore we need to iterate up to the maximum possible.
So that's why we need V minus one iterations.
And how does the check for negative cycles work?
Well, as you recall from the pseudocode,
once we've processed the graph
with our cardinality of V minus one iterations
or sooner if we have early stopping criteria,
we check the weights.
Those were the last few lines of code
in the pseudocode that we saw.
And for each edge from U to V,
if the distance to V is greater
than the sum of the distance to U
plus the edge weight from U to V,
then we know we have a negative cycle.
Let's take a look and see how that works.
So here we have a very simple graph
on three nodes: A, B, and C.
And you can see in the left-hand example here
that we have a negative cycle weight.
So we have three plus two minus seven
gives us a negative two cycle weight.
And to run Bellman-Ford, we have three nodes
so we're gonna need to run two iterations.
And we initialize our values, this is our starting node
so we set that to zero.
We set these to infinity, and then we run our algorithm.
And so we go from A to C and we find this path to C
from A of weight two, and then we go from C to B
and we find this path here of weight negative five
which is two minus seven from C.
And then we go from B to A
and we discover a path to A
that's negative five plus three is negative two.
Of course, that's our cycle weight.
And you notice that we've discovered a path.
The shortest path to A is not just to stay put at A,
but actually to go around this negative cycle
and now we have a distance of negative two from A to itself.
And that's really at the root of the problem here.
If we do this again,
remember we're starting from these points here
so negative two plus two gives us zero from A
and then we get negative seven from C
and then negative seven plus three is negative four from B
and of course the cycle weight is negative two
so we've gone from zero to negative two to negative four.
So now we perform this check to see
if we have a negative cycle and you can see here right away
that we have negative four here plus two.
Zero is greater than that value.
Negative four plus two is negative two,
zero is greater than negative two.
And so right here,
we see this is the edge that violates that condition
and we know we have a negative cycle.
And so this is how we detect negative cycles
in the Bellman-Ford algorithm.
So at this point,
Bellman-Ford would return an error telling us
that it had found a negative cycle in our graph.
So that sums up the major differences
between Bellman-Ford and Dijkstra.
And again, if you know
you have all non-negative edge weights,
use Dijkstra because it's much more efficient,
but if you do have negative edge weights
and no negative cycles, then Bellman-Ford is the way to go.
And that wraps this up.