FoundationMultiple choice
Converting between currencies · Part 1 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.
You want the conversion path between two currencies that uses the fewest trades, ignoring the rates. Which algorithm finds it in time?
- ABreadth-first search from the source
- BDepth-first search, stopping at the first path found
- CDijkstra’s algorithm with every edge weight set to one, which is guaranteed to find the shortest path
- DFloyd–Warshall over the whole graph
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