Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
Dijkstra's algorithm requires the weights to be non-negative. Your idea translates directly using logarithms, but you need all your weights $\geq 1$. Of course, you could use Bellman-Ford (ex. find the interpretation for the negative cycle). –  dtldarek Jan 6 '13 at 23:11
    
So should I use Bellman-Ford algorithm assuming there are no "negative" circle, i.e. circles that let you earn? –  haemhweg Jan 6 '13 at 23:14
1  
Well, Bellman-Ford will detect (and even find) some negative cycle if it exists, so there is no need for an assumption, but yeah, B-F would be a solution. –  dtldarek Jan 6 '13 at 23:16
    
@dtldarek: That should have been an answer. –  Rahul Jan 29 '13 at 20:50
    
@RahulNarain Being a comment it is very close to the question ;-) –  dtldarek Jan 29 '13 at 21:41

2 Answers 2

up vote 2 down vote accepted

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.

share|improve this answer

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.

share|improve this answer
    
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$. –  Rahul Jan 29 '13 at 20:48
    
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? –  user60141 Jan 29 '13 at 21:22
    
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$. –  Rahul Jan 29 '13 at 21:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.