# Does Dijkstra's algorithm work when I multiply weights of successive nodes?

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?

-
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
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

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.
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
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