Advanced Graphs
Weighted shortest paths and connectivity beyond plain BFS/DFS — Dijkstra, Union-Find, and minimum spanning trees.
Try answering in your head first, then click a question to check the model answer.
Q1.Explain why Dijkstra's algorithm requires non-negative edge weights to guarantee correctness.(show answer)
Dijkstra's greedily finalizes a node's shortest known distance once it's popped from the priority queue, assuming no future discovery could ever produce a shorter path to it — which is only true if all remaining edge weights are non-negative (since adding more non-negative edges can never decrease a path's total). With a negative edge, a longer-looking path discovered later could still turn out shorter overall, but the algorithm has already "locked in" (and moved past) a distance it won't reconsider — producing an incorrect result. Bellman-Ford handles negative weights correctly instead, at the cost of higher time complexity.
Q2.Why is a min-heap used in an efficient implementation of Dijkstra's algorithm?(show answer)
At each step, Dijkstra's needs to pick the unvisited node with the smallest known tentative distance — a min-heap gives O(log n) extraction of that minimum instead of an O(n) linear scan over all unvisited nodes, which is what makes the overall algorithm run in roughly O((V + E) log V) rather than O(V²) for a naive implementation.
Q3.What is a topological sort, and what real-world problem does it model?(show answer)
A topological sort orders the nodes of a Directed Acyclic Graph (DAG) so every edge points from an earlier node to a later one in the ordering — modeling any "must happen before" dependency structure, like course prerequisites (can't take course B before completing its prerequisite A) or build systems (can't compile a module before its dependencies). If the graph has a cycle, no valid topological ordering exists, since that would require some task to happen both before and after another.
Q4.How does Kahn's algorithm compute a topological sort using BFS?(show answer)
Compute each node's in-degree (number of incoming edges). Start a queue with all nodes that have in-degree 0 (no prerequisites). Repeatedly dequeue a node, add it to the result, and decrement the in-degree of each of its neighbors — enqueuing any neighbor whose in-degree drops to 0. If the result includes every node at the end, the sort succeeded; if fewer nodes were processed than exist in the graph, a cycle prevented some nodes from ever reaching in-degree 0.