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