Graph Search And Weighted Paths

What's being tested

Tests graph modeling, weighted path optimization, and choosing the right search strategy under constraints. You should recognize when to use BFS, Dijkstra-style priority queues, greedy heaps, or multiplicative-to-additive transforms for paths like currency exchange.

Patterns & templates

• BFS on grids — O(R*C) time for unweighted moves; track (row, col, time/state) when obstacles or timing constraints change reachability.

• Dijkstra with heapq — use for nonnegative weighted shortest paths; O((V+E) log V) and skip stale heap entries with if cost > dist[node].

• Maximum product path — for exchange rates, maximize $\prod r_i$ using a max-heap, or transform to shortest path with edge weight $-\log(r_i)$.

• Bellman-Ford for arbitrage — detects negative cycles after -log(rate) conversion; use when cycles can improve value indefinitely.

• Greedy capital selection — sort projects by required capital, push affordable profits into a max-heap, repeat k times; O(n log n + k log n).

• Visited-state design — include all variables that affect future options: position, time parity, remaining resources, current capital, or chosen count.

• Early exit carefully — valid for BFS first target and Dijkstra popped target, not for arbitrary DFS or when later cycles can improve value.

Common pitfalls

Pitfall: Treating currency exchange as normal shortest path without handling multiplication; use max-product logic or -log(rate).

Pitfall: Marking a grid cell visited only by (r, c) when time or resource state changes whether it is reachable.

Pitfall: Using DFS for weighted paths; it may find a path, but not the optimal path without exhaustive search or dynamic programming.

Practice these

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