Skip to content

Shortest Paths — Dijkstra and Friends

Dijkstra inherits from: BFS + a greedy choice + a priority queue. Data structure: graph + min-heap। Thinking tweak: সবসময় cheapest known path আগে expand করো।

Inheritance-টা, খুলে বলা

Dijkstra-র দুই-তৃতীয়াংশ তোমার হাতে আগে থেকেই আছে:

Dijkstra = BFS                      (explore outward from a source)
         + greedy choice            (process the CHEAPEST frontier node next)
         + priority queue           (the heap from ../08-heap-priority-queue/
                                     serves "cheapest" in O(log n))

BFS unweighted graph-এ কাজ করে কারণ তার queue ঘটনাক্রমে nodes-কে distance order-এ ছাড়ে — প্রতিটা edge-এর cost 1, তাই "first discovered" মানেই "cheapest"। Weights যোগ করো, সেই ভাগ্য মরে যায়: মোট cost 3-এর একটা 2-edge route, cost 10-এর একটা 1-edge route-কে হারাতে পারে, কিন্তু plain BFS 1-edge route-টাকেই আগে মুকুট পরিয়ে দিত।

মেরামতটা একটাই substitution: FIFO queue-টা বদলে path cost-এ key করা একটা min-heap বসাও। এখন পরে যে node ছাড়া হয় সে আগে queue হওয়া node না — সে হলো smallest known total cost-এর node। সেই একই "first release is final" theorem ফিরে আসে — hop count-এর বদলে cost-এর জন্য।

Thinking tweak-টা, গল্পের আকারে

তুমি তোমার home city থেকে travel time map করছ। তোমার কাছে আছে একটা frontier: "যেসব candidate route-এর কথা আমি জানি, তাদের total time সহ।" Greedy move-টা: সবসময় cheapest candidate route-টা আগে দেখো।

এটা নিরাপদ কেন? ধরো cheapest candidate বলছে "city X, total 7 ঘণ্টা।" X-এ কি কোনো undiscovered route এর চেয়ে দ্রুত হতে পারে? তাকে অন্য কোনো candidate route ধরে বেরোতে হতো — কিন্তু বাকি প্রতিটা candidate-এর cost এখনই ≥ 7 ঘণ্টা, আর extra edges শুধু আরও যোগ করে (weights non-negative)। তাই 7-ই final। X-কে stamp করো, তার outgoing edges relax করো, repeat।

ওই শেষ clause-টা — extra edges শুধু আরও যোগ করে — হলো load-bearing assumption। মনে রেখো; নিচে এটাই ভাঙে।

Algorithm-টা

import heapq

def dijkstra(adj, start):
    """adj: {u: [(v, w), ...]} with weights w >= 0.
    Returns dict of final shortest costs from start."""
    dist = {start: 0}
    done = set()                            # nodes with FINAL distances
    heap = [(0, start)]                     # (cost so far, node)

    while heap:
        cost, node = heapq.heappop(heap)    # cheapest known route anywhere
        if node in done:
            continue                        # stale heap entry: skip (lazy deletion!)
        done.add(node)                      # this cost is now provably final
        for nxt, w in adj[node]:
            new_cost = cost + w
            if nxt not in dist or new_cost < dist[nxt]:
                dist[nxt] = new_cost        # found a better route: "relax"
                heapq.heappush(heap, (new_cost, nxt))
    return dist

../08-heap-priority-queue/patterns.md-এর lazy deletion trick-টা খেয়াল করো: কোনো node-এ better route পাওয়া গেলে আমরা তার পুরোনো heap entry শিকার করতে যাই না — একটা নতুন, সস্তা entry push করি আর stale-টাকে পরে ভেসে উঠতে দিই, যেখানে if node in done: continue তাকে ফেলে দেয়। দুটো heap pattern, হুবহু reuse করা।

Binary heap সহ complexity: O((V + E) log V) — প্রতিটা edge একবার push করতে পারে, প্রতিটা push/pop একটা log দেয়।

একটা ছোট্ট dry run

        (4)
    A -------- B
    |         /|
 (1)|     (1) |(5)
    |   /     |
    C -------- D
        (8)

From A:  heap=[(0,A)]
pop (0,A): final A=0. push (4,B) (1,C).            heap: (1,C) (4,B)
pop (1,C): final C=1. push (1+1=2,B) (1+8=9,D).    heap: (2,B) (4,B) (9,D)
pop (2,B): final B=2  <- the 2-edge route A-C-B beat the direct A-B (4)!
           push (2+5=7,D).                          heap: (4,B) (7,D) (9,D)
pop (4,B): B already done -> stale, skip.
pop (7,D): final D=7.
pop (9,D): stale, skip.  Result: A=0 C=1 B=2 D=7

যে frame-এ stale (4,B) skip হলো, সেটাই পুরো lazy-deletion idea — এক লাইনে।

Negative edges কেন এটা ভেঙে দেয়

Dijkstra-র safety proof দাঁড়িয়ে ছিল এর উপর: path extend করলে সেটা কখনো সস্তা হতে পারে না। একটা negative edge ঠিক সেটাই — এমন এক extension যা path-কে সস্তা করে দেয় — তাই proof-ও, algorithm-ও, ভেঙে পড়ে।

Concrete failure:

    A --(2)--> B
    A --(5)--> C
    C --(-4)--> B          true cheapest A->B is 5 + (-4) = 1

Dijkstra cost 2-তে B pop করে তাকে FINAL stamp মেরে দেয় — greedily, আত্মবিশ্বাসে, ভুলভাবে। C-র মধ্য দিয়ে সস্তা route-টা (cost 1) পরে discover হয়, কিন্তু B already done, আর কখনো re-examine হয় না। ওই greedy stamp-টাই bug: negative edge থাকলে, "cheapest so far" আর "cheapest forever" না।

(Common interview follow-up: "সব weight positive করতে শুধু একটা constant যোগ করলেই তো হয়?" না — সেটা বেশি-edge-ওয়ালা route-গুলোকে অসমভাবে penalize করে, কোন route cheapest সেটাই বদলে দেয়।)

Bellman-Ford, ধৈর্যশীল বিকল্পটা (সংক্ষিপ্ত sketch)

Bellman-Ford greed পুরোপুরি ছেড়ে দেয়। সে শুধু প্রতিটা edge relax করে, পরপর V−1 বার:

def bellman_ford(n, edges, start):           # edges: list of (u, v, w)
    INF = float("inf")
    dist = [INF] * n
    dist[start] = 0
    for _ in range(n - 1):                   # longest simple path has n-1 edges
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w        # relax
    # one MORE full pass: anything still improving sits on a negative cycle
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            return None                       # negative cycle reachable: no answer
    return dist

কাজ করে কেন: pass k-এর পরে, ≤ k edges ব্যবহার করা প্রতিটা shortest path সঠিক; কোনো shortest path-এর V−1-এর বেশি edge লাগে না। Cost: O(V·E) — Dijkstra-র চেয়ে অনেক ধীর, কিন্তু negative edges-এ সমস্যা নেই, আর সে negative cycles detect করে (যেখানে "shortest"-এর আর কোনো মানে থাকে না, কারণ চিরকাল loop করলে cost কমতেই থাকে)। K-pass structure-টা "cheapest with at most k hops" problem-ও solve করে, যেমন Cheapest Flights Within K Stops।

কোন algorithm কখন — মুখস্থ করার table

Situation Algorithm Queue-like structure Cost
Unweighted (every edge = 1) BFS plain queue (deque) O(V + E)
Weights are only 0 or 1 0-1 BFS deque: 0-edges push FRONT, 1-edges push BACK O(V + E)
Non-negative weights Dijkstra min-heap O((V + E) log V)
Negative weights possible Bellman-Ford none (just edge passes) O(V · E)
Negative cycle detection Bellman-Ford (extra pass) none O(V · E)
All-pairs, small dense graph Floyd-Warshall (later topic) none (triple loop) O(V^3)

0-1 BFS row-টা তার এক-লাইনের intuition পাওয়ার দাবিদার: মাত্র দুটো edge cost থাকলে একটা deque নিজেকে free-তে sorted রাখতে পারে — 0-edge cost বাড়ায় না, তাই তার endpoint current node-এর মতোই urgent (push front); 1-edge-এর endpoint এক ধাপ পরে অপেক্ষা করে (push back)। BFS-এর দামে পুরো heap-ছাড়া Dijkstra behavior।

Interview-এ জোরে বলার মতো progression: queue → deque → heap। BFS → 0-1 BFS → Dijkstra। প্রতিটা step আরও fancy "who's next?" structure-এর বিনিময়ে generality কেনে।

Common mistakes (সাধারণ ভুল)

  • Negative weights-এ Dijkstra চালিয়ে output বিশ্বাস করা (সে দিব্যি চলে — নিঃশব্দে ভুল)।
  • (cost, node)-এর বদলে (node, cost) push করা — heap তখন node id দিয়ে sort করে। Tuple-এ priority-টা আগে আসতেই হবে।
  • if node in done: continue লাইনটা বাদ দেওয়া — correctness সাধারণত টিকে যায়, কিন্তু stale entry গুলো পুরো re-expand হয় আর running time খারাপ হয়।
  • BFS-ধাঁচে push-এর সময় nodes-কে done mark করা। Dijkstra-তে কোনো node-এর প্রথম push-এ তার final cost না-ও থাকতে পারে; শুধু প্রথম pop-এ থাকে।
  • Distance "update" করতে heap পুনর্নির্মাণ করা — শুধু improved entry-টা push করো (বাকিটা lazy deletion সামলায়)।
  • BFS-ই যথেষ্ট (unweighted) এমন জায়গায় Dijkstra ব্যবহার করা — সঠিক, কিন্তু একটা অপ্রয়োজনীয় log factor আর ভুল করার মতো বেশি code।

Trigger words

"Cheapest", "fastest", "minimum cost/time/effort", "network delay", edges-এ weights, "probability of success on a path" (একটা product maximize করো — probabilities-এর max-heap-এ Dijkstra), "minimum possible maximum along a path" (minimax — Dijkstra variant, যেমন Swim in Rising Water)।

Representative problems

Proof সহ reference treatment: cp-algorithms Dijkstra। Dry run সহ working code থাকে implementation.py-তে। এই folder-এর theory-র শেষ stop: topological-sort.md।