How do I find the longest path in a weighted graph?

Question

If I am given a data structure with currency conversion rates:

a list of currency relationships with exchange values. (INR - USD)

Then how can I find the best exchange rate from currency1 to currency2?

My thought process: Method 1:

if I take the list of exchange values and convert it to a graph - adjacency list and a weight list ( since this seems to be like a weighted graph problem), I can use DFS to find all possible paths and then keep a track of the path that generates the highest exchange rate (so I will multiply every conversion rate that comes in the path and store it. whenever a path generates a better conversion rate then I update this variable, therefore I have the max)

Please comment on the correctness of this algorithm. Am I thinking correctly? Would this generate the correct result?

A problem I see right away is that this is very inefficient since it would take exponential time.

Method 2: Can I just negate all the conversions and use Bellman Ford? Since Bellman Ford is used to find least costing paths in a weighted graph.

Thanks. Any guidance would be truly appreciated

Answer 1

Your intuition is correct- you could use DFS, and it would give you the best exchange rate (the shortest path by weight), but it would be extremely slow for large graphs.

Your second method (Bellman Ford) is a much better idea. As you mention, you'll have to multiply the exchange rates / edge weights, rather than add them, but this shouldn't pose any issues.

I assume you already worked this out, but for anyone referencing this in the future- you cannot use Dijkstra's algorithm nor its descendants like A*, because the graph, in spirit, has negative cycles. You could find a conversion rate less than 1, and potentially exploit this to get an overall lower minimum conversion rate (which you then just invert the two currencies, for a a maximum conversion rate in the opposite direction).

A mathematical digression:

A way to see this more clearly- imagine we have a few conversion rates, between 3 pairs of currencies- A, B, and C. Assuming the units check out, the overall conversion rate R across these three exchanges would be R = A * B * C. Another way we could write this would be R = e ^ log(A * B * C), where e is Euler's number, and log() is the natural logarithm (we could just as well have used 10 and log10(), or any other base). Rewriting this using the rules of logarithms, we can get R = e ^ (log(A) + log(B) + log(C)), and finally log(R) = log(A) + log(B) + log(C).

Now, if we don't care about the actual value of R, just which is largest / smallest (or we're willing to perform some exponentiation to get it), we can just settle for computing log(R), or the log of the exchange rate. The benefit to this is that the weights, while transformed to their logarithms, are added together, not multiplied. This allows us to use traditional implementations of graph algorithms unchanged (we just give them log(weight) instead of weight). If we try to give it something that would normally be between 0 and 1, we see that log(x) actually becomes negative, exposing the true nature of that edge, and the potential negative cycles it may create.

Summary

You'll want to probably use Bellman-Ford, and you should be fine just replacing addition with multiplication. If you have an existing implementation at hand, but which utilizes addition to combine edge weights, you can easily cheat by passing it the log() of the edge weight instead, and things will work "automagically".