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

3.5.10 · Coding › Graphs

Single-source shortest paths ek aisi graph mein jahan non-negative edge weights hon.

WHAT hai yeh problem?

Hum ek array $d i s t []$ rakhte hain jahan $d i s t [v]$ hamare abhi tak ka best known distance hai. Yeh sab ke liye $\infty$ se shuru hota hai, sivaay $d i s t [s] = 0$ ke, aur jab hum shorter routes discover karte hain to hum ise chota karte hain (relaxation).

WHY greedy kaam karta hai? (key derivation)

Claim (wo invariant jo hume prove karna hai): Jab hum frontier se smallest tentative distance wale vertex $u$ ko pop karte hain, tab $d i s t [u]$ pehle se hi true shortest distance hai.

Worked example First principles se derivation

Contradiction ke liye maano ki true shortest distance $δ (u) < d i s t [u]$ hai jis moment hum $u$ ko finalize karte hain.

Real shortest path $s ⇝ u$ ko kisi point pe finalized vertices ke set se bahar nikalna padega. $y$ ko uss path ka pehla unfinalized vertex maano, jo finalized $x$ ke through reach hua hai (edge $x \to y$ se).
Kyunki $x$ finalized hai, $d i s t [x] = δ (x)$ sahi hai, aur hum pehle se edge $x \to y$ ko relax kar chuke hain, isliye $d i s t [y] \leq δ (x) + w (x, y) = δ (y)$ .
Kyunki edges non-negative hain, $y$ se $u$ tak ke baaki path ka weight $\geq 0$ hai, isliye $δ (y) \leq δ (u)$ .
Chain karne pe: $d i s t [y] \leq δ (y) \leq δ (u) < d i s t [u]$ .
Lekin humne $u$ ko minimum tentative-distance vertex ki tarah choose kiya tha, isliye $d i s t [u] \leq d i s t [y]$ . Contradiction! ∎

Yeh step kyun? Non-negativity exactly ek baar use hoti hai — " $\geq 0$ " wale point pe. Ise hata do aur proof collapse ho jaata hai, aur precisely yahi reason hai ki Dijkstra negative edges ke saath fail karta hai.

HOW: 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, memorized nahi

Har edge zyada se zyada ek push trigger kar sakta hai (har successful relaxation pe ek), isliye heap mein zyada se zyada $O (E)$ entries hoti hain.

Pops: zyada se zyada $O (E)$ pops, har ek $O (lo g V)$ (heap size $\leq E \leq V^{2}$ hai, aur $lo g V^{2} = 2 lo g V$ ).
Pushes: zyada se zyada $O (E)$ , har ek $O (lo g 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

C ko B se pehle kyun pop kiya? Step 1 ke baad, heap mein B(4) aur C(1) hain. Hum minimum, C ko pop karte hain. Yeh greedy order hi correctness guarantee karta hai — aur yahi wajah hai ki C ki relaxation baad mein B ko 4 se 3 pe improve karti hai.

Common mistake Steel-manned common errors

1. "Longest path ke liye weights negate kar do / negative edges handle karo." Kyun sahi lagta hai: relaxation symmetric lagta hai. Reality: proof ka " $\geq 0$ " step mar jaata hai. Negative edge ke saath ek finalized vertex ko baad mein aur sasta path mil sakta hai. Fix: negative edges ke liye Bellman-Ford ( $O (V E)$ ) use karo.

2. Vertex ko pop time ki jagah push time pe visited mark karna. Kyun sahi lagta hai: "Maine pehle hi update kar diya, dobara kyun jaun?" Reality: ek vertex ka distance pop hone se pehle abhi bhi decrease ho sakta hai. Fix: sirf tab finalize karo jab non-stale distance ke saath popped ho.

3. Lazy heap ke saath stale-entry skip bhool jaana. Kyun sahi lagta hai: code chhote inputs pe "kaam" karta hai. Reality: tum outdated distances se dobara relax karte ho → galat answers ya waste of work. Fix: if d > dist[u]: continue rakho.

4. Dijkstra tab use karna jab sirf unweighted shortest path chahiye. Plain BFS $O (V + E)$ hai — $lo g V$ unnecessarily mat pay karo.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Tum ghar pe ho aur town ke har ghar tak pahunchne ka sabse fast time jaanna chahte ho. Tum ek timer shuru karte ho. Roads alag-alag minutes lagte hain chalne ke liye. Har ghar pe tumhara ek "abhi tak ka best time" wala sticky note hai. Tum hamesha us nearest ghar ko jaate ho jise tune abhi finalize nahi kiya, kyunki ek baar jab tum wahaan fast way se pahunch gaye, koi slower ghar tumhe shortcut nahi de sakta (sab roads positive time lete hain — koi magic road nahi hai jo minutes wapas de). Tum use "done" stamp karte ho aur uske neighbors ke sticky notes update karte ho. Repeat. Priority queue bas ek smart tarika hai jisse hamesha nearest not-done ghar quickly milta hai.

Flashcards

Dijkstra kaun si problem solve karta hai?

Source

s

se ek graph mein saare vertices tak single-source shortest paths, jahan non-negative edge weights hon.

"Relaxation" kya hai?

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

update karna jab

u

ke through jaana sasta ho.

Dijkstra ko non-negative edges kyun chahiye?

Correctness proof use karta hai "baaki path ka weight ≥ 0 hai" takki popped min-distance vertex already final ho; negative edges ise tod dete hain kyunki ek longer path sasta ho sakta hai.

Ek vertex ka distance kab finalized hota hai?

Jab use priority queue se popped kiya jaata hai non-stale distance ke saath (push/relax hone pe nahi).

Binary heap ke saath time complexity kya hai?

O ((V + E) lo g V)

Fibonacci heap kaun si complexity deta hai?

O (E + V lo g V)

amortized

O (1)

decrease-key ke zariye.

if d > dist[u]: continue line kya karti hai?

Lazy-deletion approach mein stale heap entries skip karti hai (ek vertex multiple baar push hota hai; sirf uska pehla/best pop matter karta hai).

Negative edges ke liye kaun sa algorithm use karein?

Bellman-Ford,

O (V E)

(ya all-pairs ke liye Johnson's).

Unweighted shortest path ke liye kaun sa algorithm?

BFS,

O (V + E)

— koi heap ki zaroorat nahi.

Greedy invariant proof mein

y

kya hai?

u

tak true shortest path pe pehla unfinalized vertex; jo finalized predecessor

x

ke zariye already relax ho chuka hai.

Connections

Bellman-Ford algorithm — negative edges handle karta hai, $O (V E)$
BFS — Dijkstra BFS ban jaata hai jab saare weights 1 ke barabar hon
A* search — Dijkstra + admissible heuristic
Priority Queue (Binary Heap) — $lo g V$ ke peeche ka engine
Greedy algorithms — exchange/invariant arguments greedy ko kyun justify karte hain
Prim's algorithm — same heap-driven skeleton, alag relaxation (MST nahi SSSP)
Johnson's algorithm — negative-edge graphs pe Dijkstra run karne ke liye reweighting