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

Single-source shortest paths in a graph with non-negative edge weights.

WHAT is the problem?

We keep an array $dist[]$ where $dist[v]$ is our current best known distance. It starts as $\infty$ for everyone except $dist[s]=0$ , and we shrink it as we discover shorter routes (relaxation).

WHY does greedy work? (the key derivation)

Claim (the invariant we must prove): When we pop the vertex $u$ with the smallest tentative distance from the frontier, $dist[u]$ is already the true shortest distance.

Worked example Derivation from first principles

Suppose for contradiction that the true shortest distance $\delta(u) < dist[u]$ at the moment we finalize $u$ .

The real shortest path $s \rightsquigarrow u$ must leave the set of finalized vertices at some point. Let $y$ be the first unfinalized vertex on that path, reached via finalized $x$ (with edge $x\to y$ ).
Since $x$ is finalized, $dist[x]=\delta(x)$ is correct, and we already relaxed edge $x\to y$ , so $dist[y] \le \delta(x)+w(x,y) = \delta(y)$ .
Because edges are non-negative, the rest of the path from $y$ to $u$ has weight $\ge 0$ , so $\delta(y) \le \delta(u)$ .
Chaining: $dist[y] \le \delta(y) \le \delta(u) < dist[u]$ .
But we chose $u$ as the minimum tentative-distance vertex, so $dist[u] \le dist[y]$ . Contradiction! ∎

Why this step? The non-negativity is used exactly once — at " $\ge 0$ ". Remove it and the proof collapses, which is precisely why Dijkstra fails with negative edges.

HOW: the algorithm

dijkstra(G, s):
    dist[v] = INF for all v;  dist[s] = 0
    PQ = min-heap with (0, s)
    while PQ not empty:
        (d, u) = PQ.pop_min()
        if d > dist[u]: continue        # stale entry, skip
        for each edge (u, v, w):
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                PQ.push((dist[v], v))    # lazy: leaves old entry behind
    return dist

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

Complexity — derived, not memorized

Each edge can trigger at most one push (one per successful relaxation), so the heap holds at most $O(E)$ entries.

Pops: at most $O(E)$ pops, each $O(\log V)$ (heap size is $\le E \le V^2$ , and $\log V^2 = 2\log V$ ).
Pushes: at most $O(E)$ , each $O(\log V)$ .
Initialization: $O(V)$ .

Worked example

Graph (directed): A→B(4), A→C(1), C→B(2), C→D(5), B→D(1), source A.

Step	Pop	dist updates	dist after
init	—	$A=0$	A0 B∞ C∞ D∞
1	A(0)	C: 0+1=1, B: 0+4=4	A0 B4 C1 D∞
2	C(1)	B: 1+2=3<4 ✓, D: 1+5=6	A0 B3 C1 D6
3	B(3)	D: 3+1=4<6 ✓	A0 B3 C1 D4
4	D(4)	none	done

Why pop C before B? After step 1, the heap has B(4) and C(1). We pop the minimum, C. This greedy order is what guarantees correctness — and it's why C's relaxation later improves B from 4 to 3.

Common mistake Steel-manned common errors

1. "Just negate weights for longest path / handle negative edges." Why it feels right: relaxation looks symmetric. Reality: the proof's " $\ge 0$ " step dies. With a negative edge a finalized vertex could later get a cheaper path. Fix: use Bellman-Ford ( $O(VE)$ ) for negative edges.

2. Marking a vertex visited at push time instead of pop time. Why it feels right: "I already updated it, why revisit?" Reality: a vertex's distance may still decrease before it's popped. Fix: finalize only when popped with a non-stale distance.

3. Forgetting the stale-entry skip with a lazy heap. Why it feels right: code "works" on tiny inputs. Reality: you re-relax from outdated distances → wrong answers or wasted work. Fix: keep if d > dist[u]: continue.

4. Using Dijkstra when you only need unweighted shortest path. Plain BFS is $O(V+E)$ — don't pay the $\log V$ .

Recall Feynman: explain to a 12-year-old

You're at home and want the fastest time to reach every house in town. You start a timer. Roads take different minutes to walk. You keep a "best time so far" sticky note on each house. You always go to the nearest house you haven't finalized yet, because once you reach it the fast way, no slower house can give you a shortcut (all roads cost positive time — there's no magic road that gives back minutes). You stamp it "done" and update its neighbors' sticky notes. Repeat. The priority queue is just a smart way to always grab the nearest not-done house quickly.

Flashcards

What problem does Dijkstra solve?

Single-source shortest paths from a source

s

to all vertices in a graph with non-negative edge weights.

What is "relaxation"?

Updating

dist[v]=\min(dist[v],\,dist[u]+w(u,v))

when going through

u

is cheaper.

Why does Dijkstra require non-negative edges?

The correctness proof uses "the rest of the path has weight ≥ 0" so the popped min-distance vertex is already final; negative edges break this since a longer path could become cheaper.

When is a vertex's distance finalized?

When it is popped from the priority queue with a non-stale distance (not when it is pushed/relaxed).

What is the time complexity with a binary heap?

O((V+E)\log V)

What complexity does a Fibonacci heap give?

O(E + V\log V)

via amortized

O(1)

decrease-key.

What does the line if d > dist[u]: continue do?

Skips stale heap entries in the lazy-deletion approach (a vertex pushed multiple times; only its first/best pop matters).

Which algorithm to use for negative edges?

Bellman-Ford,

O(VE)

(or Johnson's for all-pairs).

Which algorithm for unweighted shortest path?

BFS,

O(V+E)

— no heap needed.

In the greedy invariant proof, what is

y

The first unfinalized vertex on the true shortest path to

u

; already relaxed via finalized predecessor

x

Connections

Bellman-Ford algorithm — handles negative edges, $O(VE)$
BFS — Dijkstra reduces to BFS when all weights equal 1
A* search — Dijkstra + admissible heuristic
Priority Queue (Binary Heap) — the engine behind the $\log V$
Greedy algorithms — why exchange/invariant arguments justify greed
Prim's algorithm — same heap-driven skeleton, different relaxation (MST not SSSP)
Johnson's algorithm — reweighting to run Dijkstra on negative-edge graphs

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Dijkstra ka basic idea simple hai: source se paani chhodo, jo city pehle reach hoti hai uska shortest distance utna hi final ho gaya. Hum ek dist[] array rakhte hain — shuru me sab infinity, source ka 0. Phir priority queue (min-heap) se hamesha sabse closest unfinalized vertex nikalte hain, use "done" mark karte hain, aur uske neighbours ko relax karte hain: agar dist[u] + w < dist[v] ho to update kar do.

Greedy kyun chalta hai? Kyunki edges non-negative hain. Jab tum minimum distance wala vertex pop karte ho, koi bhi lamba raasta use sasta nahi bana sakta — kyunki extra edges sirf weight badhayenge, ghatayenge nahi. Yahi reason hai ki negative edge aate hi Dijkstra galat ho jata hai (tab Bellman-Ford use karo). Proof me bas ek hi jagah "≥ 0" use hota hai — wahi sab kuch hold karta hai.

Code me ek important trick hai: lazy heap. Decrease-key ki jagah hum naya (new_dist, v) push kar dete hain, purana stale entry heap me reh jata hai. Isliye if d > dist[u]: continue line lagao — stale pop ko skip karne ke liye. Vertex tab finalize hota hai jab pop hota hai, push pe nahi.

Complexity: har edge ek push de sakta hai, to heap me $O(E)$ entries, har operation $O(\log V)$ , total $O((V+E)\log V)$ . Fibonacci heap se $O(E + V\log V)$ . Exam aur interview dono me yeh standard answer hai — yaad rakho aur derive bhi kar pao.

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

WHAT is the problem?

WHY does greedy work? (the key derivation)

HOW: the algorithm

Complexity — derived, not memorized

Worked example

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections