# 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))

- u = EXTRACT-MAX(Q) for each edge uv:

}}}

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_{1}, c_{2}, ..., c_{k} is r_{12}r_{23}..._{r}k-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

_{12}r_{23}..._{r}k-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_{1} = 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^{3}) time, where n is the number of currencies.