Dijkstra's algorithm — greedy, priority queue, O((V+E) log V) — no negative edges: Question bank

This page is a companion to the parent Dijkstra note — every claim here refers back to the invariant, the relaxation rule, or the lazy-heap mechanics it built.

Vocabulary you need before the questions

To answer honestly you must share the exact meaning of five words. Each is anchored to a picture below.

Definition The five terms

$δ (v)$ — the true shortest-path distance from the source $s$ to vertex $v$ : the smallest total weight over all paths, the "correct answer" nature knows. Contrast with $d i s t [v]$ , our current best guess that starts too big and shrinks toward $δ (v)$ .
INF (infinity) — the starting value of $d i s t [v]$ for every non-source vertex, meaning "no path found yet." In code it's just a number bigger than any real path could ever be (e.g. float('inf') or a huge integer like $1 0^{18}$ ), so any real distance beats it in the relaxation test.
Lazy heap — a priority queue where, instead of editing a vertex's stored distance when it improves, we simply push a brand-new (smaller-distance, vertex) pair and leave the old one sitting there. "Lazy" because we never clean up; we deal with the mess only at pop time.
Stale entry — one of those leftover old pairs. When we pop it, its stored distance d is larger than the vertex's current dist[u] (a better one arrived meanwhile), so it is out of date. The guard if d > dist[u]: continue throws it away.
Finalize / "done" — the moment we pop a vertex with a non-stale distance; from then on dist[u] equals $δ (u)$ forever and is never touched again.

The figure below shows the whole flooding picture these words describe.

Figure — Dijkstra's algorithm — greedy, priority queue, O((V+E) log V) — no negative edges

And here is the worked-example graph and its heap snapshots, so the "pop C before B" question later has something concrete to point at.

True or false — justify

Every answer below is "true because…" or "false because…". A bare T/F earns nothing — the reason is the point.

Dijkstra always visits vertices in order of increasing final distance from the source.

True — the pop order is exactly non-decreasing distance, because the min-heap always yields the smallest tentative value and (with non-negative edges) that value is already final. This is the "water reaches closest cities first" ordering.

If a graph has one negative edge but no negative cycle, Dijkstra still gives correct answers.

False — a single negative edge already breaks the "

\geq 0

" step of the invariant proof, so a vertex finalized early can later gain a cheaper path that is never re-examined. Use Bellman-Ford algorithm.

Adding a large positive constant

C

to every edge weight, running Dijkstra, then subtracting, recovers correct shortest paths.

False — a path with more edges gets more

C

's added, so a 5-edge path and a 2-edge path are shifted by different totals; the reweighting is path-length dependent, changing which path is shortest. (Correct constant-shift reweighting needs vertex potentials — see Johnson's algorithm.)

Dijkstra with all edge weights equal to

1

produces the same shortest-path distances as BFS.

True — with unit weights the shortest distance equals the fewest edges, which is exactly what BFS computes. Dijkstra just pays an unnecessary

lo g V

; prefer BFS for unweighted graphs.

If dist[v] never changes after the first time we relax it, then v had no shorter path.

False in general — dist[v] can be relaxed multiple times and decrease each time before v is popped; it only becomes final at pop. "First relaxation is final" is a common trap.

Once a vertex is pushed onto the priority queue, we can safely mark it visited.

False — its tentative distance may still shrink before it is popped, so marking-at-push finalizes a possibly-wrong value. Finalize only when popped with a non-stale distance.

With a lazy heap, the same vertex can be popped more than once.

True — since we push a new pair instead of decreasing a key, duplicate entries accumulate; the second-and-later pops are stale and skipped by if d > dist[u]: continue.

Dijkstra requires the graph to be connected.

False — unreachable vertices simply keep dist = INF and are never popped; the algorithm terminates fine. Connectivity is not assumed anywhere in the proof.

Dijkstra works on both directed and undirected graphs.

True — the relaxation rule only asks "is there an edge

u \to v

?"; an undirected edge is just two directed edges. Non-negativity is the only structural requirement.

Removing the if d > dist[u]: continue line makes Dijkstra produce wrong shortest-path distances.

False — the final dist[] values still come out correct, because a stale pop can only try to relax with an already-larger d and every such relaxation fails the < test. What you lose is efficiency: you waste time re-scanning neighbors from outdated entries. Keep the line, but for correctness of the numbers it is an optimization, not a fix.

Spot the error

Each item describes a buggy belief or code choice. Name what breaks.

"I finalize a vertex the moment I update its distance."

The error is finalizing at relaxation time instead of pop time. The distance you locked in may still be improved by a cheaper route discovered later, giving wrong finals.

"To find the longest path I just negate all weights and run Dijkstra."

Negating makes every weight negative, destroying non-negativity — the invariant collapses. Longest-path in general graphs is NP-hard; Dijkstra cannot be reused this way.

"My PQ stores only the vertex id, and I look up its distance when I pop."

Without storing the distance snapshot in the heap you cannot detect stale entries (the whole point of comparing popped d against current dist[u]), so lazy deletion silently fails.

"I initialize dist[s] = 0 but leave all others at 0 too."

Non-source vertices must start at INF; starting them at 0 means no relaxation ever fires (dist[u]+w < 0 is false), so you return all zeros.

"I stop as soon as I pop the target t, so I skip the stale-check."

Early-exit at the target is valid, but you must still verify the pop of t is non-stale — a stale t pop carries an inflated distance and would return a wrong answer if you trust it.

"I use Dijkstra to build a Minimum Spanning Tree."

Wrong relaxation quantity — MST minimizes edge weight to the tree

w (u, v)

, Dijkstra minimizes total path weight

d i s t [u] + w (u, v)

. You want Prim's algorithm, same heap skeleton, different key.

"A* is always faster than Dijkstra so I use A* everywhere."

A* search only helps with a good admissible heuristic toward a specific target; for all-destinations SSSP or with a zero heuristic it degenerates to plain Dijkstra with extra overhead.

Why questions

Reasoning, not recall — explain the mechanism. (Recall $δ (v)$ = true shortest distance, $d i s t [v]$ = current guess, from the vocabulary box above.)

Why does the correctness proof use non-negativity exactly once, and where?

At the step "the rest of the path from

y

u

has weight

\geq 0

", giving

δ (y) \leq δ (u)

. That single inequality is what guarantees the popped-min vertex can't be beaten later — remove it and the chain of inequalities breaks.

Why is popping the minimum tentative distance the crucial choice?

It ensures

d i s t [u] \leq d i s t [y]

for every still-unfinalized

y

, which contradicts the assumption that a cheaper path to

u

exists. Any non-min pop order forfeits this guarantee.

Why does a lazy heap let us avoid a decrease-key operation?

Instead of finding and shrinking an existing entry (

O (lo g V)

but with bookkeeping), we just push a fresh smaller pair and ignore the old one at pop time. Simpler code, same asymptotics with a binary heap.

Why is the complexity

O ((V + E) lo g V)

and not

O (V^{2} lo g V)

The heap holds at most

O (E)

entries (one per successful relaxation), so pops and pushes total

O (E)

, each

O (lo g V)

; plus

O (V)

init. The

lo g

is over heap size

\leq E \leq V^{2}

, and

lo g V^{2} = 2 lo g V

. See Priority Queue (Binary Heap).

Why does a Fibonacci heap improve the bound to

O (E + V lo g V)

It offers amortized

O (1)

decrease-key, so the

E

relaxations cost

O (E)

total instead of

O (E lo g V)

; only the

V

extract-mins keep the

lo g

Why does Dijkstra count as a greedy algorithm rather than dynamic programming?

It commits to a locally-best choice (nearest unfinalized vertex) and never revisits it, justified by an exchange/invariant argument rather than by tabulating all subproblems.

Why can we relax the same edge

u \to v

only once effectively?

Because

u

is finalized before we relax its outgoing edges, and once finalized its dist[u] never changes — so relaxing

u \to v

again would use the same values and change nothing.

In the worked-example graph (second figure), why does the heap pop C(1) before B(4) even though B was updated first?

The heap orders by distance, not by insertion; C sits at distance 1 versus B at 4, so C is finalized first — and that is exactly what lets edge C→B relax B from 4 down to 3. The greedy order pays off.

Edge cases

The scenarios people forget to test.

What happens on a graph with zero-weight edges?

Perfectly fine — non-negative includes zero. The invariant's "

\geq 0

" holds with equality; those neighbors may be finalized at the same distance in some pop order.

What does Dijkstra return for a vertex unreachable from the source?

It stays at INF (the "no path yet" sentinel from the vocabulary box) — never pushed, never popped — correctly signalling "no path exists". No special-casing needed.

What if the source has a self-loop

s \to s

with weight

w \geq 0

Relaxation checks

d i s t [s] + w < d i s t [s]

, i.e.

w < 0

, which is false for

w \geq 0

, so dist[s]=0 is never overwritten. Self-loops are harmless.

What if two different paths to a vertex have equal total weight?

dist[v] records the shared minimum; which predecessor you keep depends on relaxation order and is an arbitrary but valid shortest path. All ties are correct answers.

What about a graph with multiple edges (parallel edges) between the same pair, different weights?

Relaxation naturally keeps the cheapest — each parallel edge is tried, and only the one giving a smaller dist[u]+w sticks. No preprocessing required.

What happens on a single-vertex graph (just the source)?

dist[s]=0 is pushed, popped, has no outgoing edges to relax, PQ empties — the algorithm returns {s:0} immediately. A clean degenerate base case.

What if every edge weight is identical (say all

= 7

Distances become

7 \times (fewest edges)

, so the pop order matches BFS layer-by-layer; Dijkstra reduces to a weighted BFS with a constant multiplier.

Recall One-line self-test

Cover the reveals above. If you can state why each trap is a trap (invariant, pop-vs-push finalization, lazy staleness, non-negativity) without peeking, you own the concept — not just the code.

Connections

Bellman-Ford algorithm — the fallback when non-negativity fails
BFS — the unit-weight / equal-weight degenerate case
A* search — Dijkstra plus a target heuristic
Priority Queue (Binary Heap) — where the $lo g V$ and the decrease-key story live
Greedy algorithms — the invariant/exchange justification
Prim's algorithm — same heap, different relaxation key
Johnson's algorithm — correct reweighting for negative edges