Shortest Path And Graph Traversal

What's being tested

These problems test graph modeling, shortest-path selection, and traversal correctness under different input shapes: grids, directed trees, weighted graphs, and path-reconstruction strings. Interviewers are checking whether you choose the right traversal primitive—BFS, Dijkstra, DFS/Union-Find, or topological-style reconstruction—and can justify complexity and edge cases.

Patterns & templates

• Multi-source BFS for nearest-distance grids — initialize queue with all gates, expand level by level; O(mn) time, O(mn) space.

• Dijkstra’s algorithm for non-negative weighted graphs — adjacency list plus min-heap priority_queue; O((V+E) log V) time.

• Directed tree validation — track parent[node], detect two-parent violations, then run cycle detection with DFS or Union-Find.

• Path reconstruction from labeled edges — build start_tag -> fragment, identify unique source, walk links; detect missing links, branches, and cycles.

• Preprocessing for repeated queries — sort/prefix arrays for budget queries, then binary search via bisect_left / upper_bound; avoid per-query scans.

• Graph representation choice — use adjacency lists for sparse graphs, matrices only for dense or tiny graphs; clarify directed vs undirected edges.

• Shortest-path gotchas — BFS only works for unit weights; use Dijkstra for positive weights and Bellman-Ford only if negative edges are possible.

Common pitfalls

Pitfall: Using DFS to compute shortest distance in an unweighted grid; BFS is the correct tool because it explores by distance layers.

Pitfall: Marking nodes visited too early in Dijkstra; skip stale heap entries by checking if dist > best[node]: continue.

Pitfall: Solving the “extra directed edge” as only cycle detection; a valid rooted tree also requires exactly one parent per non-root node.

Practice these

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