Build fluency in the vocabulary of finding shortest paths by repeatedly relaxing the closest unvisited node's neighbors.
0 / 5 completed
1 / 5
At standup, a dev mentions repeatedly picking the closest unvisited node from a priority queue and relaxing its neighbors' distances, to find the shortest path from a single source to every other node in a graph with non-negative edge weights. What is this algorithm called?
Dijkstra's algorithm is exactly this: it repeatedly pulls the closest unvisited node from a priority queue and relaxes, meaning potentially improves, the tentative distances of that node's neighbors, until every node's shortest distance from the source is finalized. A hash collision is an unrelated hash-table concept about two keys sharing a bucket. This closest-first, relax-neighbors approach is exactly why Dijkstra's algorithm finds correct shortest paths efficiently, as long as every edge weight is non-negative.
2 / 5
During a design review, the team picks Dijkstra's algorithm for a routing feature specifically because it processes nodes in order of increasing distance from the source, guaranteeing each node's distance is finalized the moment it's popped from the priority queue. Which capability does this provide?
Processing nodes in order of increasing distance provides a correctness guarantee that no node's shortest distance will ever need to be revised after it's finalized, since with non-negative edge weights, any path through an unvisited node would already be at least as long as the current node's distance, so nothing popped later could ever produce a shorter route to an already-finalized node. Visiting nodes in an arbitrary order would offer no such guarantee, since a later-discovered path might still turn out to be shorter. This finalize-in-distance-order guarantee is exactly what makes Dijkstra's algorithm correct without needing to revisit finalized nodes.
3 / 5
In a code review, a dev notices a shortest-path feature explores every possible path between two nodes exhaustively and compares their total lengths at the end, instead of using an ordered, priority-queue-driven approach. What does this represent?
This is a missed opportunity to use Dijkstra's algorithm, since exhaustively exploring every possible path between two nodes can grow explosively as the graph gets larger, while a priority-queue-driven approach finalizes each node's shortest distance incrementally, never revisiting a node once its distance is settled. A cache eviction policy is an unrelated concept about discarded cache entries. This exhaustive-path-enumeration pattern is exactly the kind of inefficiency a reviewer flags once the graph has non-negative edge weights and an ordered approach would apply.
4 / 5
An incident report shows a routing service's response time degraded sharply on larger graphs, because it exhaustively enumerated every possible path between two nodes instead of using a priority-queue-driven shortest-path algorithm. What practice would prevent this?
Implementing the routing logic with Dijkstra's algorithm finalizes each node's shortest distance incrementally using a priority queue, instead of exhaustively enumerating every possible path, which is exactly the fix for the degraded response time described in this incident. Continuing to exhaustively enumerate every path regardless of graph size is exactly what caused performance to collapse as the graph grew. This priority-queue-driven approach is the standard fix for shortest-path routing over a graph with non-negative edge weights.
5 / 5
During a PR review, a teammate asks why the team reaches for Dijkstra's algorithm instead of a simpler breadth-first search, given that breadth-first search also explores a graph level by level from a source node. What is the reasoning?
Breadth-first search finds the shortest path measured purely by the number of edges traversed, which is only correct when every edge is treated as equally weighted, while Dijkstra's algorithm correctly accounts for edges having different non-negative weights, always finding the path with the smallest total weight even when that path uses more edges than an alternative. The tradeoff is that Dijkstra's algorithm needs a priority queue and a bit more bookkeeping than breadth-first search's simple queue. This is exactly why breadth-first search suffices for an unweighted graph, while Dijkstra's algorithm is required the moment edge weights genuinely differ.