And in fact, there's no further changes. Once we have the shortest path stream,

which, we know from this example, because it's similar to one we did before then

there's going to be no, no changes to it. You're not going to find any edges that

successfully relax. And so, go through and, try them all, and

in the end we have a shortest path stream. So that is an example of a Bellman-Ford

algorithm, on a simple, simple graph. Here's the visualization of the

Bellman-Ford algorithm running on a bigger graph.

And here's what it looks like after four passes, seven, ten, thirteen.

And this graph has 100 something vertices. And it finds the tree in a relatively

small number of passes. And we'll talk about the performance in a

second of. One thing is to be sure that the algorithm

works. And there's a couple of ways to prove it.

And again, the reason the proof has to be done with care is that there could be

edges with negative weights but no negative cycles.

The idea of the proof is that after you've done the i for pass, you've found the

shortest path containing at most i edges. And, and we'll leave that proof for the

book. Now there is a couple of ways to improve

the Bellman-Ford algorithm in practice. And, the most important one is that if you

didn't change the distance to a vertex during one pass,

Then you don't have to worry about it in the next pass.

You don't have to worry about it, it's edges in the next pass.

And so, what we do in practice, is if you just maintain a queue of the vertices that

we found shorter paths to, in each path. We want to make sure that we keep, at

most, one copy of each vertex on the queue.

Otherwise, you could wind up with situations where, the, queue, size of the

queue, blows up. But that's easy to do, with, a vertex

index array to keep track of that. And so, in the worst case, you could have

all the vertices on the queue for, And then therefore all the edges relaxed, in

every one of the V passes. But in practice not too many vertices

really get relaxed. So, this is a, a quick summary of the

algorithms that we've looked for, for, shortest paths, And, we didn't do the code

for Bellman-Ford. We've done enough code today.

It's quite simple code that you'll find in the book over on the book site.

So, probably the simplest algorithm is when there are no directed cycles.

And that's when we just topologically sort the vertices and then go through that list

and relax every edge. So that's linear time.

You relax all the edges in the graph and that's it.

And that works even if there are negative weights.

If there's no negative weights but there maybe cycles, then Dijkstra's algorithm

works. And then we looked at E log V algorithms

which are slightly faster depending on what kind of heap you use.

The Bellman-Ford algorithm which works with negative weights as long as it's no

negative cycles it's if, if you do the q you can get the in, in practice it turns

out to be linear time for the times of graphs that arise in practice.

Although in principle the worst case it could be E times V which is much to slow.

So, directed cycles make the problem harder.

You need a Dijkstra instead of top logical sort.

Negative weights definitely make the problem harder.

Because you might need, to, get the worst case of Bellman-Ford.

And negative cycles, in the presence of negative cycles, it actually makes the

problem intractable. And we'll talk about that a little bit at

the end of the course. One thing that you can do with the

Bellman-Ford algorithm is to at least find, find out if there's a negative

cycle. In one practical reason to do that is

maybe it has something to do with something else specified in the problem.

And so if you can detect a negative cycle and deal with it that would be useful.

And we'll look at another important practical reason for finding negative

cycles in just a second. So anyway, since its a useful thing to do

we're going to add two methods to the API. And that is does the graph have a negative

cycle and in an interval? If it does have a negative cycle please

give it to me. So for this graph, it would return true.

And then it would give an iterable that would have these three edges that give me

the negative cycle. So, the, observation or the way to find a

negative cycle is to realize that what will happen with a Bellman-Ford algorithm

if there's a negative cycle is that it'll every, every path through, it'll basically

go around the cycle. Well not every pass in the, in the whole

length in the cycle. It'll get stuck in a loop going around the

cycle depending on the order of vertices. And it'll update and just get stuck going

around the, around the cycle. So by testing what happens after

Bellman-Ford is done, even if there's negative cycles present, we can find the

negative cycles and that, in fact, If some vertex is updated in the last

phase of the Bellman-Ford algorithm then there's a negative cycle.

And not only that. Edge 2v is the last edge, on that cycle.

That's the way you got to v. And you can trace back to find the cycle.

So just run the Bellman-Ford algorithm and if some vertex gets, get updated, the last

time through it means there's a negative cycle.

In practice actually, you don't have to wait till the last phase.

You can check these two entries for negative cycles, more frequently.

But anyway, it's possible to find a negative cycle.

And let's look at an application. This is an application that it really

motives some people to understand the shortest paths to algorithms.

And the idea is currency exchange. And so these are typical numbers that you

might see in a newspaper table, or nowadays in an app on your mobile device

that gives the exchange rates for various currencies.

So to convert a dollar to euros using factor of points 0.741, I compute Euros

too, Great Britain pounds, 0.888, and so forth.

So this table is a table of exchange rates.

And the problem is, is there an arbitrage opportunity?

So what is an arbitrage. Well arbitrage is when just by making

exchanges according to the legal rates in the table you can make money.

So say we had a $1000. And then these are the going rates.

Well we can convert that $1000 into 741 Euros.

So now, if we take those 71 Euros and convert them into Canadian dollars it

works out that we get 1,012.206 Canadian dollars.

And if we take those Canadian dollars and convert them back to U.S.

Dollars, it works out that we have $1,007. Well that's arbitrage and that's

interesting. If we could go ahead and do for well let

say $10,000 then would make $70 on the deal or a $100,000 would make $700 or

maybe a million dollars would make $7,000 or maybe a billion would make $7,000,000.

No reason to stop there. With arbitrage opportunity you're making

money off the system. So of course there's intense interest in

looking for opportunities like this. Course in modern financial market.

It's there's many more things that you can trade than currencies.

And these tables are big and complex. And the market is suppose to take care of

eliminating these opportunities. But if you are using a computer and you've

got a fast algorithm for finding negative cycles in directed graphs then maybe you

can find the opportunity and take advantage of it before the market.

So let's look at how it works. What we do is again model the situation

with a graph. So we're going to have a vertex for every

currency. And then on the edge corresponding to

every transaction or every entry in the table so this is actually a complete

directed graph. And the weight is equal to the exchange

rate. And what we are trying to find is a

directed cycle whose product of edge weights is greater than one.

So that doesn't look like a shortest path problem although it's close.

And actually it's very close. To convert this to a shortest path problem

what we want to do is just take logs. If instead of using the exchange rate, we

take minus the log of the exchange rate. And then multiplying turns to addition for

looking for multiplying the exchange rates.

That's the same as summing the logs. And, we took minus log it means that what

we're looking for when we're trying to find products bigger than one.

We're looking for a directed cycle whose sum of edge weights is less than zero.

Find a directed cycle whose sum of edge weights is less than zero in a complete

digraph. That's the negative cycle detection

problem, and we just saw that, we can, do that with the, Bellman-Ford algorithm.

And again, in a huge, directed graph in a modern trading situation, that's an

extraordinarily valuable algorithm, and you can believe that you know,

There are people out there running these algorithms in order to detect and take

advantage of arbitrage opportunities. And if you don't have a fast algorithm, if

you're using a slow one it'll be gone before you can take advantage of it.

That's a fine example of the value of building efficient algorithm for a

practical problem. So here's our summary of short as fast

today. We've seen some great, classic algorithms

that are, important and extraordinarily useful.

First one is Dijkstra's algorithm which is, a fine, efficient workhorse algorithm

that you see used, every day. And it's a, a grass search algorithm that

is, similar to, Prim's, depth for search and rep for search that we've seen before

and we'll see again if the graphs are, have no cycles which is a situation that

arises in several important applications. We can do better than Dykstra's algorithm.

It's easier. And also, negative weights are no problem,

which enables us to solve scheduling problems in other examples If there's

negative weights and negative cycles we can detect negative cycles.

And if there aren't any negative cycles, we can find shortest paths.

In, the general problem is intractable, and we'll come back to that.

But the key point that I want people to remember from today's lecture is that

shortest path is our first real example of a general problem solving model where

there's a lot of important practical problems that we cast solve as shortest

path problems. Number one and number two we have fast

solutions to those problems, with these classic algorithms that we've talked about