10
$\begingroup$

The concrete example is:

I am given n currencies and pairwise exchange rates, and I have to change say dollars for euros. And I don't have to change money directly, for example, I could change dollars to British pounds first and then to euros and make more money than I would have by direct exchange. So my first idea was to draw complete graph with exchange rates as weights of edges and use Dijkstra's algorithm with a small change, I multiply weight, not sum. Actually it seems to be logical: if I go through a path and each time make appropriate multiplications I get number of units (in currency that corresponds to the node I have come to) I would have after these exchanges. And on each iteration of Dijkstra's algorithm if I see that the way I exchange the money at this step is better than previous one for this node (if visited) then I change the value. So when I finish a tree I can easily find a shortest path between to nodes, i.e. optimal way to exchange money from one currency to all another. Is there something what contradicts this idea?

Thanks in advance, Cheers

$\endgroup$
0

3 Answers 3

Reset to default
7
$\begingroup$

As @dtldarek has answered in the comments, your proposed approach is exactly the same as doing the traditional Dijkstra's algorithm on the logarithms of the exchange rates. However, Dijkstra's algorithm requires all edge weights to be nonnegative, which will only happen if all your exchange rates are at least $1$ (unlikely), so this approach cannot be guaranteed to work. On the other hand, the Bellman-Ford algorithm finds shortest paths in the presence of negative weight edges. So, you should label your edges with the logarithms of the exchange rates, and then perform the Bellman-Ford algorithm.

$\endgroup$
1
  • $\begingroup$ Provided there's no negative cycles... I think the only solution will be to modify Bellman-Ford to prune updates when the newly added parent is already present in the path, which implies an extra cost of factor O(log(V)) in case you can detect a cycle in a path in logarithmic time. Otherwise, O(V). $\endgroup$ Commented Oct 13, 2017 at 9:35
0
$\begingroup$

Also note: if you get two different answers from $u$ to $v$ (ofcourse, while using log of rates) then there is a negative cycle (explained below). thus, unlimited money. if you know you cannot get unlimited money, well then just do it in O(1) you got the rates and you will get no better than this answer.

why would we have negative cycle if we have two different answers? ans: you are taking two different paths from u to v and getting two different answers, path1 -> ans1, and path2 -> ans2 (best answer)

do this. go from u to v using path2, then from v to u using path1 you will reach back to u having more money than you had initially. (why? because edge a to b is log(x) and edge b to a is -log(x) think for a while, i don't know how to explain.)

repeat and you got infinite money.

Of course this approach would be more reasonable if we had some charge say 1% for each transaction. then we would add edges a to b as log(x) + log(1.01) and b to a as -log(x) + log(1.01)

that would be a better question.

$\endgroup$
-1
$\begingroup$

Since you originally do not have negative weights, you can do the following: score = -log(1 - score/max(score)), then use Dijkstra's as usual. score/max_score is in [0,1], and you want multiplicative weights, so you use log to get the same effect through addition (since log(x1*x2*...*xN) = log(x1) + ... + log(xN)). But since your scores are now in [0,1], negative log ensures that the scores will never be negative, but unfortunately it has reversed the problem and now finds the longest multiplicative path. Subtracting score/max_score from 1 reverses it again, ensuring that it finds the multiplicative shortest path.

$\endgroup$
3
  • $\begingroup$ The asker wants the weight of the path to be the product of the weights of its edges. Your approach gives $1\big/\big((1-x_1/x_{\max})(1-x_2/x_{\max})\cdots(1-x_n/x_{\max})\big)$ instead, which has little to do with $x_1x_2\cdots x_n$. For example, consider what happens when there is one path with a single edge of weight $1$ and another path with two edges of weight $0.1$ and $2$, and $x_{\max}=2$. $\endgroup$ Commented Jan 29, 2013 at 20:48
  • $\begingroup$ Will we get the multiplicative shortest path, but just with different scoring? The intuition seems correct, but you are right, when I look at what you have as the end result, it doesn't seem correct. Where is the flaw in the intuition? I suppose saying "it reverses the problem" and then subtracting it from 1 is not rigorous enough. The transformation itself must mess up the weights such that I won't get the shortest path? $\endgroup$ Commented Jan 29, 2013 at 21:22
  • $\begingroup$ This should be a comment, not an answer. The point of doing logs is to transform $x_1x_2\cdots x_n$ into $\log x_1+\log x_2+\cdots+\log x_n$. The problem is that your transformation doesn't preserve this property. After you do the transformation, you get $-\log(1-x_1/x_{\max})-\log(1-x_2/x_{\max})-\cdots-\log(1-x_n/x_{\max})$, which as I said in my previous comment no longer has anything to do with what we wanted in the beginning, $x_1x_2\cdots x_n$. $\endgroup$ Commented Jan 29, 2013 at 21:46

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.