What does Dijkstra's algorithm compute on a travel-time road map, and in what order does it finalize vertices?
answer
- "shortest" is about cost, not hop count
- one source, every destination
- the queue is keyed by tentative distance
- pops come out in increasing total cost
- popped means finalized forever
basics
~20 sDijkstra computes the minimum total travel time from one source to every reachable intersection - cheapest total weight, not fewest road segments. Vertices are finalized in non-decreasing distance order, so once one is popped its distance never changes.
solid answer
~50 sDijkstra solves the single-source shortest-path problem on a graph with non-negative weights. On a road map with vertices as intersections and edge weights as travel times, one run from a source gives the minimum total travel time to every reachable intersection, plus predecessor pointers you can walk backwards to recover each route. It keeps a tentative distance per vertex, repeatedly extracts the vertex with the smallest tentative distance from a min-priority queue, marks it settled, and relaxes its outgoing edges: `if dist[u] + w < dist[v]` then `dist[v] = dist[u] + w`. Because all weights are non-negative, the popped minimum can never be improved later, so vertices are finalized in non-decreasing distance order. That ordering is why you can stop early the moment your destination is popped - but not when it merely first receives a finite tentative value.
code
pseudocode · 10 lines// dist[] starts at infinity, dist[source] = 0
// Q is a min-priority queue keyed by tentative distance
while Q is not empty:
u = extract_min(Q)
settled[u] = true
for each edge (u, v) with travel_time w:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
prev[v] = u
insert_or_decrease(Q, v, dist[v])go deeper
Be ready to state, without hedging, that this finds minimum total weight from one source to all vertices, that it requires non-negative weights, and that a vertex's distance is final once it leaves the priority queue.
Explain the mechanics out loud: tentative distances, the relaxation test, the settled set, and why the extraction order is non-decreasing. Trace a five-vertex map on a whiteboard without losing the queue state.
Show the operational judgment: when to stop early for a single target, how to recover routes from predecessor pointers, and how to sanity-check a distance table when a route looks wrong in production.
Own the framing question - is a per-query full sweep even the right shape for the workload, or does the traffic pattern call for precomputed structures, bounded search regions, or a different problem formulation entirely?
## What the algorithm is for Dijkstra's algorithm solves the **single-source shortest-path** problem on a graph whose edge weights are all non-negative. Take a courier's city map: vertices are intersections, directed edges are one-way road segments, and each edge weight is the expected travel time in seconds along that segment. Given one starting intersection, a single run produces the minimum total travel time from that start to **every** reachable intersection, and - with one extra array - the actual route to each. Two phrases in that sentence carry the whole answer. - **Single-source, all-targets.** One run is not a source-to-target query; it fills in a whole distance table. Aiming at one destination is a special case where you may stop early. - **Minimum total weight.** "Shortest" means the smallest sum of edge weights, not the smallest number of edges. A ten-segment run down an empty ring road beats a three-segment crawl through a congested centre, and Dijkstra picks the ten-segment route. Only when every edge weight is identical do "cheapest" and "fewest segments" coincide. ## The two moving parts **Tentative distances and relaxation.** `dist[v]` holds the best total travel time found so far to `v`, initialized to infinity for everything except the source, which is 0. *Relaxing* an edge `(u, v)` of weight `w` asks a single question: does routing through `u` beat what I already have for `v`? If `dist[u] + w < dist[v]`, then set `dist[v] = dist[u] + w` and record `prev[v] = u`. Relaxation is monotone - a tentative distance only ever decreases, never increases. **The min-priority queue and the settled set.** The main loop extracts the unsettled vertex with the smallest tentative distance, declares it *settled*, and relaxes its outgoing edges. Settled vertices are done; the queue holds the frontier. ## Why the pop order is the whole point The algorithm's central invariant is: **when a vertex is extracted with tentative distance d, d is its true shortest distance.** The intuition is short - any alternative route to that vertex has to leave the settled region through some frontier vertex whose own tentative distance is at least `d`, and every remaining edge on that route adds a non-negative amount, so no alternative can come in under `d`. (The formal exchange argument that greedy selection is safe belongs with greedy-correctness proofs generally; here what matters is that the invariant depends entirely on weights being non-negative.) A direct consequence: vertices leave the queue in **non-decreasing** distance order. The search expands like a ball of travel time growing outward from the source. ## Stopping early - and the classic off-by-one If you only need one destination, you may break out of the loop the instant that destination is *popped*. You may **not** stop when it first receives a finite tentative distance: at that moment the value is only the best route discovered so far, and a cheaper route through a not-yet-settled vertex may still arrive. This is the most common junior mistake in a whiteboard trace. ## Distances versus routes `dist[]` alone answers "how long"; it does not answer "which way". The `prev[]` pointers written during relaxation form a shortest-path **tree** rooted at the source. To print a route, walk `prev` from the destination back to the source and reverse the list. When several routes tie, `prev` records exactly one of them - the tie is broken arbitrarily by queue order, which is fine, since all tied routes are equally optimal. ## What it does not compute - Not the route with the fewest road segments (unless all weights are equal). - Not a minimum-total-weight spanning structure over all roads - that is a different problem with a different greedy rule. - Not all-pairs distances; that is V separate runs, or a dedicated all-pairs method. - Not anything trustworthy when a weight is negative, because the finality invariant above evaporates. A zero-weight edge, by contrast, is completely fine: non-negative includes zero, and the invariant still holds.
- You only care about one destination. When exactly may you stop, and what do you gain?Stop the moment the destination is extracted from the queue - at that instant its distance is final. You gain everything outside the ball of travel time around the source that is closer than the destination; on a large map that can be most of the graph. Stopping when the destination merely receives a finite tentative distance is wrong, because a cheaper route through an unsettled vertex may still arrive.
- The algorithm computes numbers. Where does the actual route come from?From a predecessor array written during relaxation: whenever `dist[v]` improves via `u`, record `prev[v] = u`. Those pointers form a shortest-path tree rooted at the source. To recover a route, walk `prev` from the destination back to the source and reverse. Ties among equally cheap routes are broken arbitrarily by queue order, and any one of them is a correct answer.
- Do zero-weight edges cause trouble?No. The finality argument needs weights to be non-negative, and zero qualifies: an alternative route can match a settled distance but never beat it. Zero-weight edges just mean several vertices share the same distance and get settled consecutively in arbitrary order. Only strictly negative weights break the invariant.
Think of dye spreading through the road network at unit speed: the order intersections get stained is exactly the order Dijkstra settles them.
saying these in an interview costs you the question
- Says it finds the route with the fewest edges
- Thinks one run answers only a single source-target query
- Claims a distance can still improve after the vertex is popped
- Stops as soon as the destination gets any finite distance
- Assumes the graph must be acyclic or undirected