Graph Algorithms For Routing And Conversion

What's being tested

These problems test graph modeling: represent currencies, data centers, or map locations as vertices and relationships as directed or undirected weighted edges. You must choose the right traversal or shortest-path strategy, maintain clean adjacency structures, and reason about unreachable nodes, cycles, dynamic updates, and tie-breaking. Strong solutions also explain complexity and separate domain logic—such as Haversine distance or exchange-rate multiplication—from traversal.

Patterns & templates

• Weighted directed graph for conversions: store adj[src] = [(dst, rate)]; compose rates along DFS/BFS paths while tracking visited nodes.

• Use BFS for any reachable conversion when edge count is unweighted; return immediately on target discovery, with O(V + E) time and O(V) space.

• For multiplicative paths, carry amount *= rate; avoid revisiting nodes, and define behavior for missing currencies, self-conversions, and inconsistent cycles.

• Topological sort applies only to a DAG: compute indegrees with Kahn’s algorithm or use postorder DFS; detect cycles when fewer than V nodes are emitted.

• For nearest healthy data centers, filter unhealthy nodes first, compute Haversine distance, then select the minimum with deterministic tie-breaking; scan in O(D) per query.

• For bicycle routing, use Dijkstra’s algorithm for nonnegative costs; use a priority queue and relax edges, yielding O((V + E) log V).

• For multi-criteria routes, define one scalar cost or use Pareto frontiers; do not silently optimize distance while claiming to optimize time and safety.

Common pitfalls

Pitfall: Treating exchange rates as additive weights; conversion along a path multiplies rates, while shortest-path algorithms generally compare additive costs.

Pitfall: Using topological sort on a graph that may contain cycles, or assuming DFS visitation alone proves a valid ordering without tracking the active recursion state.

Pitfall: Mixing latitude/longitude degrees with Euclidean distance; convert degrees to radians and handle antimeridian, duplicate, empty, and unreachable cases explicitly.

Practice these

The practice cards below cover the canonical variants—solve all of them and time yourself.