ExpertMultiple choice
Converting between currencies · Part 3 of 3
Currencies are the vertices of a directed graph, and each quoted exchange rate from one currency to another is an edge. There are V currencies and E quotes, and converting along a path multiplies the rates on its edges.
Some of the −log weights are negative, and a cycle with negative total weight is an arbitrage loop. How do you detect one?
- ARun Bellman–Ford: if any edge still relaxes after V − 1 rounds, a negative cycle exists
- BRun Dijkstra and flag any vertex whose final distance is negative
- CAdd a constant to every weight so that all are non-negative, then run Dijkstra
- DSort the currencies topologically and relax edges in that order, flagging any distance that turns negative on the way
The worked solution is in Premium
The answer, the full working and the one idea to take away – for this and all 1,322 questions in the bank. Answer it in practice and your working is marked, with a known mistake named when you make one.
Learn the method
More data structures and algorithms questions
- What is the maximum number of edges in a directed acyclic graph on ten vertices?Foundation
- A dependency graph has edges a → b, a → c, b → d, c → d.Foundation
- Your shortest-path graph has some negative edge weights but no negative cycles.Applied
- What is the running time of Dijkstra’s algorithm with a binary heap, on a graph…Applied
- A graph has edges A–B (weight 1), B–C (2), A–C (3), C–D (4) and B–D (5).Applied
- With both union by rank and path compression, what is the amortised cost of a…Advanced