Hi, in the previous lesson you learned to find shortest paths in the graph

with non-negative edge weight.

In this lesson, you will learn to find shortest paths

even in the graphs where some of the edge weights can be negative.

We will explore that using a problem about currency exchange,

which doesn't seem to have anything to do with shortest paths.

But we will soon find out it does.

So the problem about currency exchange is that

you are given some possibilities that you can convert currency into another.

For example, US dollars to Russian rubles,

or rubles to Euros, or Euros to Norwegian crowns.

And what you want to do is take your initial $1,000 and

convert it into Russian rubles.

Potentially doing many conversions on the way,

such that you get as many Russian rubles as you can in the end.

So one question is what is the maximum amount of rubles you can get?

And another question is actually can you get as many as you want?

And the same question about US dollars.

Can you get as many US dollars as you want?

It may seem that if you can get as many rubles as you want,

then you will also be able to get as many dollars as you want.

But that's not always the case, it depends on your restrictions.

For example, if you lived in the USSR, you might be able to get some rubles for

dollars you got from your foreign country trip.

But it's very unlikely you could buy some dollars inside USSR.

So in this problem we assume that you have some restrictions on which

directions you can convert currencies and what are the rates.

So this is an illustration from Wikipedia article called Triangular Arbitrage

which illustrates the fact that sometimes it is possible to make three trades and

exchange first dollars to Euros, then Euros to Great Britain pounds.

And then pounds to US dollars, so that you generate some profit.

In this case, given $5 million,

you generate a profit of 25,000, just by doing those three trades.

These triangular arbitrages exist very rarely and

only due to some market inefficiencies.

But in theory, this is possible.

And this example has some numbers on the edges.

For example, the rate of conversion from dollars to Euros is 0.81.

And you get 1.19 Euros per British pound.

And you get 1.46 dollars per British pound.

So given these conversion rates and of course those should also count for

commissions and any other money that you actually don't get.

So given those numbers, you determine exactly how many dollars will you get from

5 million initial if you do all the trades shown on the picture.

So we will be discussing this problem,

how much you can get of each currency and if it's actually possible

to get more of the currency you had initially doing some trades.

So how does this conversion work?

If we have some path, if we convert first from dollars to Euros then Euros to

pounds then some other conversions, then we come to Norwegian crowns and

then we finally convert them to rubles.

Then how many rubles do we get per 1 US dollar?

Well, it is determined by the product of the conversion rates written on the edges.

So for example, if for $1, we get 0.88 Euros and for

1 Euro we get 0.84 pounds, and so one, and for

1 Norwegian crowns we get 8.08 rubles.

Then for 1 US dollar we will get the product of all those numbers in rubles.

That's how conversion rates work, if you account, again, for

commissions and other payments in each trade

inside this number, which right on the edge.