# 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-র দুই-তৃতীয়াংশ তোমার হাতে আগে থেকেই আছে:

```text
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-টা

```python
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](../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

```text
        (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:

```text
    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 বার**:

```python
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](https://leetcode.com/problems/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

- [Network Delay Time](https://leetcode.com/problems/network-delay-time/) — textbook Dijkstra; answer হলো largest finished distance।
- [CSES Shortest Routes I](https://cses.fi/problemset/task/1671) — competitive-programming scale-এ Dijkstra; lazy-skip লাইনটা এখানে বাধ্যতামূলক।
- [Path With Minimum Effort](https://leetcode.com/problems/path-with-minimum-effort/) — grid-এ Dijkstra, sum-এর বদলে maximum step minimize করা।
- [Cheapest Flights Within K Stops](https://leetcode.com/problems/cheapest-flights-within-k-stops/) — hop limit তোমাকে Bellman-Ford-এর pass structure-এর দিকে ঠেলে দেয়।
- [Swim in Rising Water](https://leetcode.com/problems/swim-in-rising-water/) — grid-এ minimax Dijkstra।

Proof সহ reference treatment: [cp-algorithms Dijkstra](https://cp-algorithms.com/graph/dijkstra.html)। Dry run সহ working code থাকে [implementation.py](implementation.py)-তে। এই folder-এর theory-র শেষ stop: [topological-sort.md](topological-sort.md)।