Cheapest conversion route through a fee network
Asked at Flow Traders
A network of currencies is connected by directed conversion legs, each charging a non-negative fee. Find the minimum total fee to convert from a source currency to a destination, or report that no route exists.
n = 4
edges = [(0,1,1), (0,2,4), (1,2,1), (2,3,1), (1,3,5)] # (from, to, fee)
src = 0, dst = 3
-> 3 # 0 -> 1 -> 2 -> 3 costs 1 + 1 + 1
Return the minimum total fee from src to dst, or -1 if unreachable.
Your answer
This one is open-ended. Work it through, then check your reasoning against the full solution.