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?
Thanks in advance,
Cheers
 A: 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.
A: 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.
