1. Tallest path

Here is a modified version of Dijkstra's algorithm that runs in time O(V log V + E) if implemented with Fibonacci heaps, and slightly more time if implemented in a reasonable way:

{{{TallDijkstra:

• h[s] = +infinity, h[t] = 0 for all t != s. put all vertices in a priority Q supporting EXTRACT-MAX while Q is not empty:
  • u = EXTRACT-MAX(Q) for each edge uv:
    • h[v] = max(h[v], min(h[u], c(u,v))
  return h

}}}

This is basically Dijkstra's algorithm with the order reversed and + replaced by min. The proof of correctness is essentially the same: the nodes come out of the queue in order of decreasing height, and the height of each node u is correct when it leaves because if there were a better path to u whose penultimate node was still in the queue than the one whose penultimate node set h[u] when it left, some earlier node q from this path would have h[q] > h[u] while still being in the queue and would thus have been extracted instead.

2. Exchange rates

Let r_ij be the number of units of currency c_j that can be bought with one unit of currency c_i. Then the return from a sequence of trades going through a sequence of currencies c₁, c₂, ..., c_k is r₁₂r₂₃..._rk-1,k_{, and we make a profit if c}1 _{= c}k,, and this product is greater than 1. Take a logarithm of the product and negate it; now we have

• -log(r₁₂r₂₃..._rk-1,k_{) = -∑log(r}i,i+1_{) = ∑ -log(r}i,i+1,,),

and we now make a profit if the sum is less than zero and c₁ = c_k. Since we can't assume that all currencies are reachable from a single starting currency, we use Floyd-Warshall to detect the existence of any negative cycle by looking for some i with d(i,i) < 0. This takes O(n³) time, where n is the number of currencies.