Dijkstra — সবচেয়ে ছোট পথ

১ · সমস্যাটি — ঢাকা থেকে চট্টগ্রাম, সবচেয়ে কম সময়ে

ঈদের ছুটিতে আপনি ঢাকা থেকে গাড়িতে চট্টগ্রাম যাবেন। রাস্তা একটি নয়: সোজা মহাসড়ক ধরে কুমিল্লা হয়ে যাওয়া যায়, নরসিংদী ঘুরে যাওয়া যায়, চাঁদপুরের দিক দিয়েও যাওয়া যায়। প্রতিটি রাস্তায় সময় আলাদা — কোথাও জ্যাম, কোথাও ফাঁকা। প্রশ্নটি সরল: কোন পথে গেলে মোট সময় সবচেয়ে কম? মোবাইলের ম্যাপ অ্যাপ প্রতিদিন কোটি কোটি মানুষের জন্য ঠিক এই প্রশ্নের উত্তর দেয় — প্রতিটি মোড় একটি বিন্দু, প্রতিটি রাস্তার টুকরো একটি রেখা, আর রেখার গায়ে লেখা সেই মুহূর্তে পার হতে কত সময় লাগবে।

পর্ব ৩৯-এর ভাষায় এটি একটি graph: শহরগুলো vertex, রাস্তাগুলো edge. নতুন জিনিস হলো প্রতিটি edge-এর গায়ে একটি সংখ্যা — তার ওজন (weight). এমন গ্রাফকে বলে weighted graph. রাস্তা দুই দিকেই চলে বলে আমাদের উদাহরণটি undirected; একমুখী রাস্তা থাকলে হতো directed graph. নিচের মানচিত্রে সংখ্যাগুলো মিনিটে যাত্রার সময় (বোঝার সুবিধায় বানানো সংখ্যা, আসল সময় নয়)। ঢাকা–কুমিল্লার সরাসরি রাস্তায় এই মুহূর্তে বড় জ্যাম, তাই সেখানে 200.

                 Narsingdi
                /         \
            60 /           \ 90
              /             \
        Dhaka ------200------ Cumilla ----60---- Feni ----110---- Chattogram
              \             /                     /
           150 \           / 70                  /
                \         /                     /
                 Chandpur ---------100----------

একটি পথের ওজন মানে তার সব edge-এর ওজনের যোগফল। u থেকে v-এর সবচেয়ে কম ওজনের পথকে বলে shortest path, আর সেই ওজনকে লেখা হয় δ(u, v) (ডেল্টা). পথ না থাকলে δ = ∞. আমাদের প্রশ্নটির নাম single-source shortest path (SSSP): একটি নির্দিষ্ট উৎস s (এখানে ঢাকা) থেকে প্রতিটি vertex-এর δ(s, v) বের করা। মজার ব্যাপার, শুধু চট্টগ্রামের উত্তর চাইলেও সেরা জানা পদ্ধতিগুলো পথে পড়া প্রায় সব শহরের উত্তর বের করে ফেলে — এক গন্তব্যের প্রশ্ন সাধারণত এক উৎসের প্রশ্নের চেয়ে সহজ নয়।

BFS কেন যথেষ্ট নয়

পর্ব ৪০-এ BFS unweighted গ্রাফে সবচেয়ে ছোট পথ দিত — কারণ সেখানে প্রতিটি edge-এর দাম সমান, তাই “কম edge” আর “কম দূরত্ব” একই কথা। ওজন এলেই এই সমতা ভাঙে। চট্টগ্রামে যাওয়ার কয়েকটি পথ দেখুন:

BFS স্তর ধরে চলে, তাই সে চট্টগ্রামে পৌঁছায় তিন edge-এর কোনো পথে — ৩৬০ বা ৩৭০ মিনিট। অথচ সেরা পথটিতে edge চারটি, সময় ৩২০ মিনিট। ঘুরপথ কখনো কখনো আসলে দ্রুত — ঢাকার যেকোনো চালক এটি জানেন। আর সব পথ গুনে দেখাও সমাধান নয়: পথের সংখ্যা গ্রাফের আকারের সাথে exponential হারে বাড়ে।

২ · Relaxation — দূরত্বের অনুমান ধাপে ধাপে কমানো

Shortest path অ্যালগরিদমগুলো প্রতিটি vertex v-এর জন্য একটি সংখ্যা রাখে: dist[v] — “এখন পর্যন্ত s থেকে v-এ যাওয়ার যে সবচেয়ে ভালো পথ জানি, তার ওজন”. শুরুতে dist[s] = 0, বাকি সবার ∞ — কিছুই জানা নেই। তারপর একটিমাত্র কাজ বারবার করা হয়, যার নাম relaxation:

মানে: “u পর্যন্ত আমি dist[u] সময়ে যেতে পারি, তারপর এই রাস্তায় আরও w — তাহলে v-তে যাওয়ার এটি একটি নতুন পথ। আগের জানা পথের চেয়ে ভালো হলে সেটি মনে রাখি।” par[v] (parent বা predecessor) মনে রাখে v-তে আসার সেরা পথে আগের vertex কে — পথ ফিরে পেতে এটি লাগবে (অংশ ৬)। পেছনের ধারণাটি হলো: অনুমানটি সবসময় একটি ওপরের সীমা, আর প্রতিটি সফল relax সেই সীমাকে সত্যের দিকে একটু নামিয়ে আনে।

দুটি তথ্য মনে রাখুন, প্রমাণে লাগবে। (১) dist সবসময় একটি ওপরের সীমা: যেকোনো মুহূর্তে dist[v] ≥ δ(s, v), কারণ dist[v] সবসময় কোনো একটি বাস্তব পথের ওজন (বা ∞)। (২) dist শুধু কমে: relax মান বাড়ায় না। আর যখন সব edge (u, v)-এর জন্য dist[v] ≤ dist[u] + w(u, v) — অর্থাৎ আর কোনো relax কিছু বদলায় না — তখন dist-ই আসল উত্তর। একে বলে triangle inequality: δ(s, v) ≤ δ(s, u) + w(u, v), “ঘুরপথ সরাসরির চেয়ে ভালো হতে পারে না”.

তাহলে shortest path-এর সব অ্যালগরিদম আসলে একই খেলার ভিন্ন কৌশল: কোন edge কোন ক্রমে relax করব? পর্ব ৪৪-এর Bellman-Ford বলে “সব edge, V − 1 বার” — সহজ, কিন্তু O(VE). পর্ব ৪২-এর DAG-এ topological ক্রমে একবার করে — O(V + E). আর Dijkstra বলে: সবচেয়ে কাছের vertex থেকে শুরু করা, প্রতিটি vertex-এর edge ঠিক একবার।

৩ · Dijkstra-র greedy ধারণা — সবচেয়ে কাছেরটিকে চূড়ান্ত করা

অ্যালগরিদমটি vertex-গুলোকে দুই দলে রাখে: settled (যাদের দূরত্ব চূড়ান্ত) আর বাকিরা। প্রতিটি ধাপে:

1. যারা এখনো settled নয়, তাদের মধ্যে যার dist সবচেয়ে ছোট, তাকে বাছাই করুন — নাম দিন u.
2. u-কে settled ঘোষণা করুন: dist[u] এখন থেকে চূড়ান্ত।
3. u থেকে বের হওয়া প্রতিটি edge relax করুন।

এটি একটি greedy অ্যালগরিদম: প্রতিটি ধাপে সেই মুহূর্তের সেরা দেখানো পছন্দটি নেয়, আর কখনো ফিরে তাকায় না। Greedy সব সমস্যায় ঠিক উত্তর দেয় না (পর্ব ৫০), তাই এখানে প্রমাণ দরকার — অংশ ৪-এ। “সবচেয়ে ছোট dist” বারবার খুঁজতে লাগে একটি priority queue (পর্ব ২৩)। নিচের pseudocode-এ দুটি সংস্করণ — একটি সাধারণ অ্যারে দিয়ে খোঁজে, অন্যটি min-heap দিয়ে।

Pseudocode — Dijkstra (0-based vertices, every weight w >= 0)

// Version 1: plain array, O(V^2) -- good for dense graphs
dijkstraArray(G, s):
    dist[v] = INF, done[v] = false for every v;   dist[s] = 0
    repeat V times:
        u = the vertex with done[u] == false and the smallest dist[u]
        if dist[u] == INF: stop                   // everything left is unreachable
        done[u] = true                            // settle u: dist[u] is final
        for each edge (u, v, w):
            if not done[v] and dist[u] + w < dist[v]:
                dist[v] = dist[u] + w;   par[v] = u

// Version 2: binary heap + lazy deletion, O((V+E) log V)
dijkstraHeap(G, s):
    dist[v] = INF for every v;   dist[s] = 0;   push (0, s)
    while the heap is not empty:
        (d, u) = pop the smallest pair
        if d != dist[u]: continue                 // stale pair -- u was settled earlier
        for each edge (u, v, w):
            if d + w < dist[v]:
                dist[v] = d + w;   par[v] = u;   push (dist[v], v)

দ্বিতীয় সংস্করণের কৌশলটি লক্ষ করুন। কোনো vertex-এর dist কমলে heap-এর ভেতরের পুরোনো জোড়াটি খুঁজে বদলানো (decrease-key) কঠিন, তাই নতুন জোড়াটি আরেকবার push করা হয়। পুরোনোটি heap-এ থেকেই যায়; পরে সেটি বের হলে d != dist[u] দেখে চেনা যায় যে এটি বাসি — বাদ। এর নাম lazy deletion. প্রথমবার যে জোড়াটি বের হয়, তার d-ই সবচেয়ে ছোট, তাই সেটিই u-কে settle করে। এবার আমাদের মানচিত্রে পুরোটা চালিয়ে দেখুন:

শেষ পর্যবেক্ষণটি গুরুত্বপূর্ণ: vertex-গুলো দূরত্বের ছোট থেকে বড় ক্রমে settle হয় — ঠিক পুকুরের ঢেউয়ের মতো। এটি কাকতালীয় নয়, পরের অংশের প্রমাণের মূল কথা।

৪ · কেন ঠিক কাজ করে — প্রমাণ, আর ঋণাত্মক edge-এ ব্যর্থতা

দাবি (invariant): সব edge-এর ওজন ≥ 0 হলে, কোনো vertex u যখন settled হয়, তখন dist[u] = δ(s, u), আর পরে আর কখনো বদলায় না। প্রমাণটি proof by contradiction — এটি বিশ্ববিদ্যালয়, চাকরি আর ইন্টারভিউর পরীক্ষায় প্রায়ই লিখতে হয়, তাই ধাপগুলো ভালো করে দেখুন।

1. ধরে নিই দাবি মিথ্যা. তাহলে এমন একটি প্রথম vertex u আছে, যে settle হওয়ার মুহূর্তে dist[u] > δ(s, u). u ≠ s, কারণ dist[s] = 0 = δ(s, s). আর u-তে কোনো পথ আছে (নইলে δ = ∞ = dist).
2. একটি আসল সবচেয়ে ছোট পথ P নিন, s থেকে u পর্যন্ত। P শুরু হয় settled দল থেকে (s) আর শেষ হয় বাইরে (u এখনো settled নয়)। তাই P-তে একটি প্রথম vertex y আছে যে settled নয়; তার ঠিক আগের vertex x settled.
3. y-এর অনুমান ঠিক. x আগে settle হয়েছে, আর u-ই প্রথম ভুল — তাই dist[x] = δ(s, x). x settle হওয়ার সময় edge (x, y) relax হয়েছিল, তাই dist[y] ≤ δ(s, x) + w(x, y) = δ(s, y) (সবচেয়ে ছোট পথের যেকোনো অংশও সবচেয়ে ছোট পথ)। ওপরের সীমার নিয়মে dist[y] ≥ δ(s, y), তাই dist[y] = δ(s, y).
4. এখানেই লাগে “ওজন ≥ 0”. y পথ P-তে u-এর আগে, আর y থেকে u পর্যন্ত বাকি অংশের ওজন ≥ 0. তাই δ(s, y) ≤ δ(s, u).
5. বিরোধ. মিলিয়ে: dist[y] = δ(s, y) ≤ δ(s, u) < dist[u]. অর্থাৎ y-এর dist u-এর চেয়ে ছোট — তাহলে অ্যালগরিদম u নয়, y-কেই বাছাই করত। কিন্তু সে বাছাই করেছে u-কে। বিরোধ। তাই দাবি সত্য। ∎

লক্ষ করুন, ধাপ ৪ ছাড়া প্রমাণের আর কোথাও ওজনের চিহ্ন লাগেনি। যদি P-এর শেষ অংশে একটি ঋণাত্মক edge থাকে, তাহলে δ(s, y) > δ(s, u) হতে পারে — “দূরের” y থেকে ঘুরে এসে u-তে আরও কম খরচে পৌঁছানো যায়। তখন u-কে আগেভাগে চূড়ান্ত করাটাই ভুল। একটি counterexample দেখুন। এবার ওজন মানে টাকা: একটি রাস্তায় টোলের বদলে ঋণাত্মক −3 — ধরুন সেই রাস্তায় গেলে একটি পেমেন্ট অ্যাপ ৩ টাকা ক্যাশব্যাক দেয়। Directed গ্রাফ: S→A 2, S→B 4, B→A −3, A→T 1.

        2         1
   S ------> A ------> T
    \        ^
   4 \       | -3
      v      |
       ----> B

এবার কোডে, পাশাপাশি পর্ব ৪৪-এর Bellman-Ford দিয়ে — যে সব edge V − 1 বার relax করে, তাই relax-এর ক্রমের ওপর নির্ভর করে না:

#include <cstdio>
#include <vector>
using namespace std;
struct Edge { int u, v, w; };

int main() {
    const int n = 4, INF = 1'000'000'000;
    const char* nm = "SABT";                                   // 0 = S, 1 = A, 2 = B, 3 = T
    const vector<Edge> es{{0, 1, 2}, {0, 2, 4}, {2, 1, -3}, {1, 3, 1}};

    // textbook O(V^2) Dijkstra: settle the closest unsettled vertex and never touch it again
    vector<int> d(n, INF);
    vector<bool> done(n, false);
    d[0] = 0;
    for (int it = 0; it < n; ++it) {
        int u = -1;
        for (int x = 0; x < n; ++x)
            if (!done[x] && (u == -1 || d[x] < d[u])) u = x;
        done[u] = true;
        for (const Edge& e : es)                               // tiny graph: just scan every edge
            if (e.u == u && !done[e.v] && d[u] + e.w < d[e.v]) d[e.v] = d[u] + e.w;
    }

    // Bellman-Ford: relax every edge V-1 times (correct with negative edges, no negative cycle)
    vector<int> b(n, INF);
    b[0] = 0;
    for (int it = 0; it < n - 1; ++it)
        for (const Edge& e : es)
            if (b[e.u] != INF && b[e.u] + e.w < b[e.v]) b[e.v] = b[e.u] + e.w;

    for (int v = 0; v < n; ++v) printf("%c: dijkstra=%d  bellman-ford=%d\n", nm[v], d[v], b[v]);
}

S: dijkstra=0  bellman-ford=0
A: dijkstra=2  bellman-ford=1
B: dijkstra=4  bellman-ford=4
T: dijkstra=3  bellman-ford=2

INF = float("inf")
nm = "SABT"                                       # 0 = S, 1 = A, 2 = B, 3 = T
n = 4
es = [(0, 1, 2), (0, 2, 4), (2, 1, -3), (1, 3, 1)]

# textbook O(V^2) Dijkstra: settle the closest unsettled vertex and never touch it again
d, done = [INF] * n, [False] * n
d[0] = 0
for _ in range(n):
    u = min((x for x in range(n) if not done[x]), key=lambda x: d[x])
    done[u] = True
    for a, v, w in es:
        if a == u and not done[v] and d[u] + w < d[v]:
            d[v] = d[u] + w

# Bellman-Ford: relax every edge V-1 times
b = [INF] * n
b[0] = 0
for _ in range(n - 1):
    for a, v, w in es:
        if b[a] + w < b[v]:
            b[v] = b[a] + w

for v in range(n):
    print(f"{nm[v]}: dijkstra={d[v]}  bellman-ford={b[v]}")

৫ · বাস্তবায়ন — O(V²) অ্যারে, নাকি heap আর lazy deletion?

অ্যালগরিদম একটাই, খরচ নির্ভর করে “সবচেয়ে ছোট dist” কীভাবে খুঁজছি তার ওপর। গ্রাফ রাখা হয় পর্ব ৩৯-এর adjacency list-এ: প্রতিটি u-এর জন্য (v, w) জোড়ার তালিকা।

অ্যারে সংস্করণের হিসাব. V বার সবচেয়ে ছোট খোঁজা, প্রতিবার V টি ঘর দেখা — V². প্রতিটি vertex একবার settle হয়, তাই প্রতিটি edge একবার (undirected-এ দুই দিকে দুবার) relax — O(E). মোট O(V² + E), আর E ≤ V² বলে O(V²). বাড়তি জায়গা O(V). যখন প্রায় প্রতিটি জোড়ার মধ্যে edge আছে (E ≈ V²), তখন এটিই সেরা — heap সংস্করণ সেখানে O(V² log V).

Heap সংস্করণের হিসাব. প্রতিটি সফল relax একটি push. প্রতিটি vertex একবারই (প্রথম, অ-বাসি pop-এ) তার edge-গুলো relax করে, তাই সফল relax সর্বোচ্চ E টি, আর শুরুর জোড়াসহ push সর্বোচ্চ E + 1. যত push, ততই সর্বোচ্চ pop. Heap-এ কখনো E + 1-এর বেশি জোড়া থাকে না, তাই প্রতিটি কাজ O(log E) — আর E ≤ V² বলে log E ≤ 2 log V, অর্থাৎ O(log V). মোট O((V + E) log V), জায়গা O(V + E). রাস্তার মানচিত্রের মতো গ্রাফে E মাত্র V-এর কয়েক গুণ, তাই এটি প্রায় O(V log V) — দশ লাখ মোড়েও C++-এ সাধারণত এক সেকেন্ডের কম।

Decrease-key বনাম lazy deletion. পর্ব ২৩-এর indexed heap (pos[] অ্যারেসহ) ভেতরের জোড়ার key সরাসরি কমাতে পারে, তাই heap-এ কখনো V-এর বেশি জোড়া থাকে না। কিন্তু std::priority_queue বা Python heapq-এ decrease-key নেই। Lazy deletion-এ কোড চার লাইনেই শেষ, একই Big-O, শুধু heap বড় হয় (V-এর বদলে E) — এ কারণেই এটি কনটেস্টের মানক ছাঁচ। এবার পুরো প্রোগ্রাম, পথ পুনর্গঠনসহ:

#include <cstdio>
#include <functional>
#include <queue>
#include <string>
#include <utility>
#include <vector>
using namespace std;

int main() {
    const vector<string> name{"Dhaka", "Narsingdi", "Cumilla", "Chandpur", "Feni", "Chattogram"};
    const int n = (int)name.size();
    vector<vector<pair<int, int>>> adj(n);                     // adj[u] = {(v, minutes)}
    auto road = [&](int u, int v, int w) { adj[u].push_back({v, w}); adj[v].push_back({u, w}); };
    road(0, 1, 60); road(0, 2, 200); road(0, 3, 150); road(1, 2, 90);
    road(2, 3, 70); road(2, 4, 60); road(3, 4, 100); road(4, 5, 110);

    const long long INF = 1LL << 60;
    vector<long long> dist(n, INF);
    vector<int> par(n, -1);                                    // par[v] = previous city on the best path
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<>> pq;   // MIN-heap
    dist[0] = 0; pq.push({0, 0});
    while (!pq.empty()) {
        auto [d, u] = pq.top(); pq.pop();
        if (d != dist[u]) { printf("skip stale (%lld, %s)\n", d, name[u].c_str()); continue; }
        printf("settle %-10s dist=%lld\n", name[u].c_str(), d);
        for (auto [v, w] : adj[u])
            if (d + w < dist[v]) { dist[v] = d + w; par[v] = u; pq.push({dist[v], v}); }   // relax
    }
    vector<int> path;                                          // walk back from the target, then reverse
    for (int v = 5; v != -1; v = par[v]) path.push_back(v);
    printf("Dhaka -> Chattogram: %lld min via", dist[5]);
    for (int i = (int)path.size() - 1; i >= 0; --i) printf(" %s", name[path[i]].c_str());
    printf("\n");
}

settle Dhaka      dist=0
settle Narsingdi  dist=60
settle Cumilla    dist=150
settle Chandpur   dist=150
skip stale (200, Cumilla)
settle Feni       dist=210
settle Chattogram dist=320
Dhaka -> Chattogram: 320 min via Dhaka Narsingdi Cumilla Feni Chattogram

import heapq

name = ["Dhaka", "Narsingdi", "Cumilla", "Chandpur", "Feni", "Chattogram"]
n = len(name)
adj = [[] for _ in range(n)]                     # adj[u] = [(v, minutes)]
for u, v, w in [(0, 1, 60), (0, 2, 200), (0, 3, 150), (1, 2, 90),
                (2, 3, 70), (2, 4, 60), (3, 4, 100), (4, 5, 110)]:
    adj[u].append((v, w))
    adj[v].append((u, w))

INF = float("inf")
dist, par = [INF] * n, [-1] * n                  # par[v] = previous city on the best path
dist[0] = 0
pq = [(0, 0)]                                    # heapq is a MIN-heap of (dist, vertex)
while pq:
    d, u = heapq.heappop(pq)
    if d != dist[u]:
        print(f"skip stale ({d}, {name[u]})")
        continue
    print(f"settle {name[u]:<10} dist={d}")
    for v, w in adj[u]:
        if d + w < dist[v]:                      # relax
            dist[v], par[v] = d + w, u
            heapq.heappush(pq, (dist[v], v))

path, v = [], 5                                  # walk back from the target, then reverse
while v != -1:
    path.append(name[v])
    v = par[v]
print(f"Dhaka -> Chattogram: {dist[5]} min via", " ".join(reversed(path)))

settle Dhaka      dist=0
settle Narsingdi  dist=60
settle Cumilla    dist=150
settle Chandpur   dist=150
skip stale (200, Cumilla)
settle Feni       dist=210
settle Chattogram dist=320
Dhaka -> Chattogram: 320 min via Dhaka Narsingdi Cumilla Feni Chattogram

৬ · পথ ফিরে পাওয়া, একাধিক উৎস — আর নিজে চালিয়ে দেখুন

Path reconstruction আর shortest path tree

dist শুধু বলে “কত মিনিট”, চালক জানতে চান “কোন রাস্তায়”. প্রতিটি সফল relax-এ আমরা par[v] = u লিখেছি — এই predecessor array-ই পুরো উত্তর। লক্ষ্য t থেকে শুরু করে par ধরে পেছনে হাঁটুন যতক্ষণ না −1 (উৎস) আসে, তারপর তালিকাটি উল্টে দিন — ঠিক কোডের শেষ তিন লাইন। পথে k টি vertex থাকলে সময় O(k). পেছনে হাঁটা কেন ঠিক? কারণ সবচেয়ে ছোট পথের প্রতিটি শুরুর অংশও সবচেয়ে ছোট পথ — Chattogram-এর সেরা পথ Feni হয়ে গেলে, সেই পথের Feni পর্যন্ত অংশটি Feni-র সেরা পথই।

সব v-এর জন্য (v, par[v]) edge-গুলো একসাথে নিলে একটি tree পাওয়া যায়, যার root s: shortest path tree. V − 1 টি edge-এ s থেকে সবার সেরা পথ ধরা থাকে। নিচের visualiser-এ সেটি সবুজ মোটা রেখায় দেখা যাবে। সাবধান: এটি পর্ব ৪৫-এর minimum spanning tree নয় — MST মোট ওজন কমায়, এই tree প্রতিটি vertex-এর s থেকে দূরত্ব কমায়। আমাদের মানচিত্রেই দুটি আলাদা।

Multi-source — সবচেয়ে কাছের ফায়ার স্টেশন

ঢাকার প্রতিটি এলাকা থেকে সবচেয়ে কাছের ফায়ার স্টেশনে পৌঁছাতে কত সময়? প্রতিটি স্টেশন থেকে আলাদা Dijkstra চালালে k গুণ কাজ। কৌশল: সব স্টেশনকে শুরুতেই dist = 0 দিয়ে heap-এ দিন, তারপর স্বাভাবিক Dijkstra চালান। ভাবুন একটি নকল super source আছে, যার থেকে প্রতিটি স্টেশনে 0-ওজনের edge — তার একটি সাধারণ Dijkstra আর এটি হুবহু এক কাজ করে। ফল: প্রতিটি vertex-এর সবচেয়ে কাছের উৎসের দূরত্ব, এক বারেই O((V + E) log V)-এ। par ধরে পেছনে গেলে বোঝা যায় কোন স্টেশন সবচেয়ে কাছে। এটিই multi-source shortest path.

নিজে চালিয়ে দেখুন — Dijkstra visualiser

“চালিয়ে দেখুন” চাপুন। প্রোগ্রাম প্রথমে নিজে পুরোটা চালিয়ে শেষ অবস্থা দেখাবে। তারপর আবার শুরু চেপে পরের ধাপ দিয়ে একটি একটি pop দেখুন, বা ওপরের তালিকা থেকে অন্য উৎস বেছে নিন। রং: লাল = এইমাত্র settled, সবুজ = settled, হলুদ = dist জানা কিন্তু চূড়ান্ত নয়, ধূসর = ∞. বৃত্তের ভেতরের সংখ্যা dist, সবুজ মোটা রেখা = shortest path tree-র edge.

const city = ["Dhaka", "Narsingdi", "Cumilla", "Chandpur", "Feni", "Chattogram"];
const xy = [[45, 95, 33], [150, 45, -25], [200, 105, 33], [130, 185, 33], [300, 160, 33], [405, 90, -25]];   // x, y, label offset
const roads = [[0, 1, 60], [0, 2, 200], [0, 3, 150], [1, 2, 90], [2, 3, 70], [2, 4, 60], [3, 4, 100], [4, 5, 110]];
let dist, par, done, pq, cur;
const $ = id => document.getElementById(id);
const byKey = (a, b) => a[0] - b[0] || a[1] - b[1];              // smallest (dist, vertex) first
function reset() {
  const s = Number($("src").value);
  dist = city.map(() => Infinity); par = city.map(() => -1); done = city.map(() => false);
  dist[s] = 0; pq = [[0, s]]; cur = -1; draw("start at " + city[s]);
}
function step() {                        // one pop of the priority queue (a sorted array here)
  if (!pq.length) { cur = -1; draw("done: queue is empty"); return false; }
  const [d, u] = pq.sort(byKey).shift();
  if (d !== dist[u]) { cur = -1; draw(`skip stale (${d}, ${city[u]})`); return true; }
  done[u] = true; cur = u;
  for (const [a, b, w] of roads) for (const [x, v] of [[a, b], [b, a]])
    if (x === u && d + w < dist[v]) { dist[v] = d + w; par[v] = u; pq.push([dist[v], v]); }
  draw(`settle ${city[u]} at ${d}`); return true;
}
function draw(msg) {
  let g = "";
  for (const [a, b, w] of roads) {
    const [x1, y1] = xy[a], [x2, y2] = xy[b], on = par[b] === a || par[a] === b;
    g += `<line x1="${x1}" y1="${y1}" x2="${x2}" y2="${y2}" stroke="${on ? "#16a34a" : "#94a3b8"}" stroke-width="${on ? 4 : 2}"/>`;
    g += `<text x="${(x1 + x2) / 2}" y="${(y1 + y2) / 2 - 5}" class="w">${w}</text>`;
  }
  city.forEach((c, i) => {
    const f = i === cur ? "#fca5a5" : done[i] ? "#86efac" : dist[i] < Infinity ? "#fde047" : "#e2e8f0";
    g += `<circle cx="${xy[i][0]}" cy="${xy[i][1]}" r="18" fill="${f}" stroke="#334155"/>`;
    g += `<text x="${xy[i][0]}" y="${xy[i][1] + 4}">${dist[i] === Infinity ? "∞" : dist[i]}</text>`;
    g += `<text x="${xy[i][0]}" y="${xy[i][1] + xy[i][2]}" class="n">${c}</text>`;
  });
  $("g").innerHTML = g;
  $("pq").textContent = "PQ: " + (pq.sort(byKey).map(([d, v]) => `(${d}, ${city[v]})`).join(" ") || "empty");
  $("msg").textContent = msg; console.log(msg);
}
$("src").onchange = reset; $("bn").onclick = step; $("br").onclick = reset;
$("ba").onclick = () => { while (step()); };
reset(); while (step());

start at Dhaka
settle Dhaka at 0
settle Narsingdi at 60
settle Cumilla at 150
settle Chandpur at 150
skip stale (200, Cumilla)
settle Feni at 210
settle Chattogram at 320
done: queue is empty

৭ · অবস্থা যোগ করা Dijkstra, আর গ্রিডে Dijkstra

State-space Dijkstra — k টি টোল ফ্রি

অনেক সমস্যায় “কোথায় আছি” যথেষ্ট নয়, জানতে হয় “কী অবস্থায় আছি”. ধরুন আপনার কাছে একটি কুপন আছে, যা দিয়ে সর্বোচ্চ k টি রাস্তার খরচ মাফ। এখন একই শহরে দুই অবস্থায় পৌঁছানো আলাদা জিনিস: কুপন বাকি থাকলে সামনের দামি রাস্তা ফ্রি পাবেন, না থাকলে নয়। সমাধান: vertex-কে (শহর, এ পর্যন্ত ব্যবহৃত কুপন j) জোড়া হিসেবে দেখুন. প্রতিটি রাস্তা (u, v, w) থেকে দুই ধরনের edge: (u, j) → (v, j) ওজন w (টাকা দিয়ে), আর j < k হলে (u, j) → (v, j + 1) ওজন 0 (কুপন খরচ করে)। নতুন গ্রাফে সাধারণ Dijkstra, আর উত্তর হলো j-এর সব মানের মধ্যে dist[(t, j)]-এর সবচেয়ে ছোটটি। এটি state-space search-এর একটি উদাহরণ — একে “layered graph”-ও বলে: k + 1 টি তলায় একই মানচিত্রের কপি, আর 0-ওজনের সিঁড়ি দিয়ে এক তলা থেকে পরের তলায়।

  S --8--> A --8--> T
  S --3--> B --12-> T

খরচ: অবস্থা V(k + 1) টি, edge প্রায় 2E(k + 1) টি, তাই সময় O(k (V + E) log(kV)), জায়গা O(k(V + E)) — যদিও কোডে নতুন গ্রাফ বানাতে হয় না, শুধু dist[v][j] 2D অ্যারে আর heap-এ (d, v, j) তিনটি জিনিস। একই ছাঁচে আসে “জ্বালানি কতটা আছে”, “কোন চাবিগুলো হাতে” (bitmask, পর্ব ৫৫), “শেষ কোন দিকে চলছিলাম” — অবস্থার সংখ্যা ছোট রাখাই আসল নকশা।

গ্রিডে Dijkstra

একটি R × C মানচিত্রে প্রতিটি ঘরে ঢুকতে আলাদা খরচ — কাদা, পানি, পাকা রাস্তা। এখানে আলাদা করে গ্রাফ বানানোর দরকার নেই: প্রতিটি ঘর (r, c) একটি vertex, আর চার প্রতিবেশী (ওপর, নিচ, বাঁ, ডান) তার edge, ওজন = প্রতিবেশী ঘরে ঢোকার খরচ। এই grid graph-এ V = RC, E ≤ 4RC, তাই সময় O(RC log(RC)). কোডে প্রতিবেশী বের হয় dr[] = {-1, 1, 0, 0}, dc[] = {0, 0, -1, 1} অ্যারে দিয়ে, আর গ্রিডের বাইরে যাওয়া আটকাতে সীমা যাচাই। ওজন যদি শুধু 0 আর 1 হয় (যেমন “দেয়াল ভাঙলে 1, খোলা পথে 0”), তাহলে heap-এর দরকারই নেই: পর্ব ১৪-এর deque-এ 0-ওজনের প্রতিবেশী সামনে, 1-ওজনেরটি পেছনে push — এই 0-1 BFS O(V + E)-এ একই উত্তর দেয়, কারণ deque-টি সবসময় dist-এর ক্রমে সাজানো থাকে, আর তাতে কখনো দুটির বেশি আলাদা dist থাকে না।

৮ · A* search — লক্ষ্যের দিকে ঝুঁকে খোঁজা

Dijkstra-র ঢেউ সব দিকে সমানভাবে ছড়ায়। ঢাকা থেকে চট্টগ্রাম খুঁজতে গিয়ে সে উল্টো দিকের রাজশাহীর রাস্তাগুলোও ঘাঁটে — যতক্ষণ না ঢেউয়ের ব্যাসার্ধ চট্টগ্রামের দূরত্বে পৌঁছায়। একটি নির্দিষ্ট লক্ষ্য t থাকলে আমরা কি ঢেউকে t-এর দিকে ঠেলতে পারি? A* search (উচ্চারণ “এ-স্টার”) ঠিক তা করে। প্রতিটি vertex-এর জন্য একটি অনুমান h(v) ধরুন — “v থেকে t আর কতটা বাকি” — যাকে বলে heuristic. তারপর heap-এর key হিসেবে dist[v]-এর বদলে নিন f(v) = dist[v] + h(v): “এ পর্যন্ত খরচ + বাকি পথের অনুমান”. h(v) = 0 হলে এটি হুবহু Dijkstra.

• Admissible: h(v) কখনো আসল বাকি দূরত্ব δ(v, t)-এর বেশি নয় — অনুমানটি আশাবাদী। তাহলে A* সবসময় সঠিক সবচেয়ে ছোট পথ দেয়, আর t যখন heap থেকে বের হয় তখনই থামা যায়। রাস্তার মানচিত্রে দুই বিন্দুর সোজা-রেখার দূরত্ব admissible — কোনো রাস্তা সোজা রেখার চেয়ে ছোট হতে পারে না (সময় হলে সোজা দূরত্ব ÷ সর্বোচ্চ গতি)।
• Consistent: প্রতিটি edge-এ h(u) ≤ w(u, v) + h(v), আর h(t) = 0. Consistent হলে admissible-ও হয়, আর প্রতিটি vertex একবারই settle হয়। কারণটি সুন্দর: নতুন ওজন w′(u, v) = w(u, v) − h(u) + h(v) ধরলে সবগুলো ≥ 0, আর যেকোনো s–t পথের ওজন ঠিক h(t) − h(s) পরিমাণ বদলায় — সব পথে একই পরিমাণ। তাই A* আসলে এই নতুন ওজনে সাধারণ Dijkstra, আর অংশ ৪-এর প্রমাণ হুবহু খাটে।
• গ্রিডে: চার দিকে চলা আর প্রতি ধাপের খরচ অন্তত 1 হলে Manhattan distance |r − r_t| + |c − c_t| consistent. h যত আসল দূরত্বের কাছাকাছি, A* তত কম vertex ঘাঁটে; h = δ হলে (সমান f-এর জোড়ায় সমতা ঠিকভাবে ভাঙলে) সে প্রায় শুধু সেরা পথটিই হাঁটে।

Admissible নয় এমন h (যেমন সোজা দূরত্বের দ্বিগুণ) নিলে A* দ্রুত চলে কিন্তু উত্তর সবচেয়ে ছোট না-ও হতে পারে — গেমের চরিত্রের পথ খোঁজায় কখনো কখনো ইচ্ছে করেই এটি করা হয়। A* প্রকাশ করেন Peter Hart, Nils Nilsson আর Bertram Raphael, ১৯৬৮ সালে, Stanford Research Institute-এর Shakey নামের রোবটের পথ খোঁজার কাজ থেকে। কৃত্রিম বুদ্ধিমত্তার পাঠ্যবইয়ে আজও এটি অন্যতম কেন্দ্রীয় অ্যালগরিদম, আর ভিডিও গেমে পথ খোঁজার সবচেয়ে প্রচলিত পদ্ধতি।

৯ · AI-এর যুগে Dijkstra — কোড চলে, কিন্তু কি ঠিক?

“Dijkstra লিখে দাও” — যেকোনো AI কয়েক সেকেন্ডে লিখবে, আর ছোট উদাহরণে সঠিক উত্তরও দেবে। সমস্যা লুকোয় সূক্ষ্ম জায়গায়: visited চিহ্ন push-এর সময় দেওয়া, C++-এ max-heap রেখে দেওয়া, বাসি জোড়া বাদ না দেওয়া, বা ঋণাত্মক ওজনের ইনপুটে আত্মবিশ্বাসের সাথে Dijkstra চালানো। এর অনেকগুলোতে উত্তর ঠিক আসে, শুধু বড় ইনপুটে সময়সীমা পেরোয় — যা ছোট পরীক্ষায় কখনো ধরা পড়ে না।

Dijkstra-র কোডে AI সাধারণত যেসব ভুল করে

Dijkstra-র কোড যাচাইয়ের চেকলিস্ট

• অংশ ৩-এর মানচিত্র হাতে trace করে কোডের settle-ক্রম আর dist মিলিয়েছি
• একই গ্রাফে Bellman-Ford বা ছোট গ্রাফে সব পথ গোনা brute force-এর সাথে হাজারটি এলোমেলো গ্রাফে stress testing করেছি
• Edge case: পৌঁছানো যায় না এমন vertex, 0-ওজনের edge, একই দুই vertex-এর মধ্যে একাধিক edge, self-loop, V = 1
• সবচেয়ে বড় ইনপুটে dist-এর সর্বোচ্চ মান (V − 1) × সর্বোচ্চ ওজন হিসাব করে টাইপ (long long) বেছেছি
• ইনপুটে কোনো ঋণাত্মক ওজন নেই, সমস্যার বিবরণ পড়ে নিশ্চিত হয়েছি — থাকলে অন্য অ্যালগরিদম
• settle-এর সংখ্যা ঠিক পৌঁছানো vertex-এর সংখ্যার সমান, আর push E + 1-এর বেশি নয় — ছেপে দেখেছি