0:00

So now, I want to reduce this problem to the problem about shortest paths, and

Â we will do that using two standard approaches.

Â First, we don't know what to do with this product, so instead of products of

Â weights we want sums of weights, like in the shortest paths problems.

Â And we will replace products with sums by taking logarithms of weights, and

Â I will show that in a minute.

Â And another problem is that we need to maximize something in this problem,

Â while shortest paths are all about minimizing.

Â So we'll have to also negate weights to solve minimization

Â problem instead of maximization.

Â 0:36

First let's talk about taking the logarithm is a known rule that x

Â is the same as two to the power of logarithm of x over two.

Â So, we can take any product of two number, like x and y and

Â rewrite x is two the logarithm of x and y as 2 to the power of logarithm of y.

Â And then, x y is equal to 2 to the power of logarithm of x by 2 of the power of

Â logarithm as y, and now we know the rule of summing the powers.

Â So this is equal to 2 to the power of logarithm of x plus logarithm of y

Â 1:19

So if we want to maximize product effects on Y.

Â This is actually the same of maximizing the sum of logarithm of X and logarithm of

Â Y because if he sum becomes bigger then 2 to the power of the sum becomes bigger.

Â And if the sum becomes smaller, then 2 to the power of sum also becomes smaller.

Â This is true not only for 2 numbers.

Â For example, if we have 3 specific numbers.

Â 4, 1, and 1 or 2 which one to multiply.

Â On one hand, we get 2 which is 2 to the power of 1.

Â On another hand, if we sum up the logarithm Terms of 4,

Â 1, and one-half, we get sum of 2, 0, and -1.

Â And the logarithms can be both positive and negative.

Â They're positive when the number is bigger than 1 and they're negative

Â when the number is smaller than 1, and they're 0 when the number is equal to 1.

Â So in this case, we get the sum of 1, which is the same as the power to which

Â we Exponentiate our 2.

Â So you see that it works not only for 2 numbers, but also for several numbers.

Â And in general, to maximize the product of k numbers, r would EJ.

Â It is the same as to maximize the corresponding the sum of

Â logarithms of these numbers.

Â 2:43

And now that this only works if all these numbers are positive, because we cannot

Â take logarithms of negative values and we also cannot take logarithms of 0.

Â But if all the exchange rates are positive numbers, hopefully then we

Â just take logarithms and we reduce our problem of maximizing

Â product of some numbers to maximizing sum of some numbers.

Â Now, we want to go from maximization to minimization but that is easy.

Â If you want to maximize the sum of logarithms,

Â it is the same as minimize minus the sum.

Â 3:20

And we will also want to work just with the sum, not with the minus sum,

Â so we can insert this minus inside the sum incorporated.

Â And so finally, we get that maximizing

Â the sum of logarithms is the same as minimizing the sum of minus logarithms.

Â 3:38

Trading those two ideas, we've got the following reduction.

Â We replace the initial edge weights,

Â conversion weights, rei by minus algorithm of rei.

Â And we find the shortest path between the nodes corresponding to USD and

Â the nodes corresponding to RUR in the graph.

Â 3:58

And this is equivalent to the initial problem of how

Â many rubbles you can get from $1000.

Â So now, it looks like we've solved the problem

Â because we can create the currency exchange graph with the conversion rates,

Â we can replace those rates with logarithms.

Â And we can find the shortest path from USD to RUR using Dijkstra's Algorithm,

Â which were learned in the previous lesson.

Â And then, we can just do the exchanges corresponding to the shortest path in

Â the graph which you found.

Â However, that doesn't exactly work.

Â Because Dijkstra's algorithm heavily relies on the fact that the shortest path

Â from s to t goes only through vertices that are closer to s than t.

Â And this is because the edge weights are positive, but if

Â edge weights can be negative, this is no longer the case and the example is below.

Â If we used Dijkstra's algorithm as soon as it saw only two

Â edges from s to A and to B.

Â One of them with weight five, and another with weight ten.

Â It would decide that the shortest path to S to A is exactly five,

Â because we cannot improve it.

Â In this example, we can improve it.

Â We go from S to B, then from B to A, and

Â the path will be, already, minus ten, which is much less than five.

Â So Dijkstra's algorithm doesn't work in such cases.

Â Such an example is also possible in the currency exchange problem.

Â Here is a graph with realistic conversion rates between ruble, euros and U.S.

Â dollars.

Â And our goal is to convert rubles into US dollars in the most profitable way.

Â And it turns out that if we take minus logarithms of these conversion rates,

Â then although the number on the edge from Rubles to

Â US Dollars is less than the number from Rubles to Euros.

Â It is still beneficial to go through Euros to US Dollars

Â 6:02

because of the negative edge between euros and US dollars.

Â And it's true that if you multiply the conversation rate between rubles and

Â euros, and then between euros and dollars.

Â It will be slightly bigger than if we convert directly from rubles to dollars.

Â 6:39

What it means is that we can go from a to b than from B to C, than from C to A.

Â And if we add those weights we get -1.

Â So the sum of the edges on the cycle is negative.

Â And because of that, if you want to convert for example from S to A,

Â if you want to go from S to A and find the shortest path, this is not possible.

Â Because we can go from S to A, use distance of 4 But then we can just go

Â around the cycle A B C, A B C, A B C many, many times, as many as we want.

Â And the distance will only decrease.

Â So the distance from S to node A is actually minus infinity, is not defined.

Â You can do as short a path as you want.

Â And the same is true about nodes B and C of course because they are on the cycle.

Â So you can do the same thing with them.

Â And the same is also true about node D because it is reachable from the cycle.

Â So we can go to the cycle and make a lot of round trips on the cycle and

Â then go to node D from either from B or from C.

Â So all these nodes.

Â Are the infinitely close to S, like the shortest path is minus infinity.

Â And it turns out that in the currency exchange problem a cycle can potentially

Â make you a billionaire, if you are lucky and if you have enough time for that.

Â But you'll learn how to do that a little bit later in this lesson.

Â