Bellman-Ford আর Floyd-Warshall

১ · ঋণাত্মক ওজন — যখন পথ চললে খরচ কমে

পর্ব ৪৩-এ Dijkstra দেখেছেন: একটি উৎস থেকে প্রতিটি vertex-এ সবচেয়ে কম খরচের পথ, যখন সব edge-এর ওজন শূন্য বা ধনাত্মক। কিন্তু বাস্তবের খরচ সবসময় ধনাত্মক থাকে না। একটি weighted graph-এ edge-এর ওজন মানে “এই পথে গেলে কত খরচ” — আর কিছু পথে গেলে খরচ উল্টে লাভ হয়ে যায়। তখন ওজন হয় ঋণাত্মক, আর আমাদের লাগে ঋণাত্মক ওজনের edge সামলাতে পারে এমন shortest path অ্যালগরিদম।

• ক্যাশব্যাক আর বোনাস: একজন ডেলিভারি রাইডারের কাছে প্রতিটি রুটের খরচ = তেল আর সময় − কোম্পানির বোনাস। কোনো ব্যস্ত রুটে বোনাস তেলের খরচের চেয়ে বেশি হলে সেই edge-এর নিট খরচ ঋণাত্মক। bKash বা Nagad-এ কোনো নির্দিষ্ট পেমেন্টে ক্যাশব্যাক থাকলে লেনদেনের ধাপে ধাপে খরচ হিসাবেও একই ব্যাপার ঘটে।
• ভর্তুকি: কোনো রুটে সরকার বা কোম্পানি ভর্তুকি দিলে, পরিবহনের মোট খরচের গ্রাফে সেই অংশ ঋণাত্মক হতে পারে।
• শক্তি: বৈদ্যুতিক গাড়ি বা ই-বাইক ঢাল বেয়ে নামার সময় regenerative braking-এ ব্যাটারিতে কিছু শক্তি ফেরত পায়। “কত শক্তি খরচ” মাপলে উতরাইয়ের edge ঋণাত্মক।
• মুদ্রা বিনিময়: সবচেয়ে বিখ্যাত উদাহরণ — নিচে বিস্তারিত।

মুদ্রা বিনিময় আর log-এর কৌশল

ধরুন তিনটি মুদ্রার মধ্যে বিনিময় হার এরকম (হারগুলো কাল্পনিক, শুধু বোঝার জন্য): ১ ডলারে 0.92 ইউরো, ১ ইউরোতে 0.86 পাউন্ড, আর ১ পাউন্ডে 1.28 ডলার। ১ ডলার নিয়ে পুরো চক্র ঘুরলে হাতে আসে 0.92 × 0.86 × 1.28 ≈ 1.0127 ডলার — শুধু হাতবদল করেই ১ শতাংশের বেশি লাভ। একে বলে arbitrage. প্রশ্ন: বড় একটি বিনিময়-টেবিলে এমন চক্র আছে কি না, কীভাবে খুঁজবেন?

সমস্যা হলো, পথে হারগুলো গুণ হয়, আর shortest path অ্যালগরিদম ওজন যোগ করে। সমাধান logarithm: log(a × b) = log a + log b. প্রতিটি হার r-এর জন্য edge-এর ওজন দিন w = −log r. তাহলে কোনো চক্রে হারগুলোর গুণফল > 1 হওয়া মানে log-এর যোগফল > 0, অর্থাৎ −log-এর যোগফল < 0. উদাহরণে: −ln 0.92 ≈ 0.0834, −ln 0.86 ≈ 0.1508, −ln 1.28 ≈ −0.2469; যোগফল ≈ −0.0127 — ঋণাত্মক। অর্থাৎ arbitrage খোঁজা = ঋণাত্মক যোগফলের চক্র খোঁজা. এই চক্রের নাম negative cycle, আর এটি ধরাই এই পর্বের Bellman-Ford-এর একটি প্রধান কাজ।

Dijkstra কোথায় ভুল করে

Dijkstra-র মূল যুক্তি ছিল greedy: heap থেকে যে vertex সবচেয়ে কম দূরত্ব নিয়ে বের হয়, তার দূরত্ব চূড়ান্ত — কারণ অন্য যেকোনো পথ আরও বড় দূরত্বের কোনো vertex দিয়ে যাবে, আর edge যোগ করলে দূরত্ব শুধু বাড়ে। ঋণাত্মক edge এই “শুধু বাড়ে” অনুমানটিই ভেঙে দেয়। তিনটি vertex-এর ছোট একটি উদাহরণ:

আসল উত্তর dist(A) = 1, পথ S → B → A. Dijkstra-র কোনো রূপ A-কে আবার না খুললে ভুল 2 থেকে যায়, আর A থেকে যাওয়া সব পথও ভুল হয়। (Lazy deletion-এর কিছু রূপ A-কে আবার খোলে বলে এই ছোট উদাহরণে ঠিক উত্তর দিতে পারে, কিন্তু তখন সময়ের নিশ্চয়তা হারিয়ে যায় — worst case-এ exponential.) আর একটি পরিচিত ভুল সমাধান হলো “সব ওজনে একটি বড় সংখ্যা যোগ করে ধনাত্মক বানাও” — এটি কেন কাজ করে না, অনুশীলন ৩-এ নিজেই দেখবেন।

২ · Relaxation আর Bellman-Ford-এর মূল ধারণা

প্রতিটি shortest-path অ্যালগরিদমের কেন্দ্রে একটিই ছোট কাজ: relaxation. প্রতিটি vertex v-এর জন্য রাখা থাকে dist[v] — “এখন পর্যন্ত জানা সেরা খরচ” (শুরুতে উৎসের 0, বাকি সবার ∞). Edge u → v (ওজন w) relax করা মানে প্রশ্ন করা: “u হয়ে v-তে গেলে কি এখনকার চেয়ে কম খরচ পড়ে?” পড়লে dist[v] কমিয়ে দিন, আর parent[v] = u লিখে রাখুন।

Pseudocode — Bellman-Ford (0-based vertices 0..V-1, edge list E)

relax(u, v, w):
    if dist[u] != INF and dist[u] + w < dist[v]:
        dist[v] = dist[u] + w;  parent[v] = u;  return true
    return false

bellmanFord(V, E, s):
    dist[*] = INF;  parent[*] = -1;  dist[s] = 0
    repeat V-1 times:                         // one "round"
        changed = false
        for each edge (u, v, w) in E:  if relax(u, v, w): changed = true
        if not changed: break                 // early termination
    for each edge (u, v, w) in E:             // the V-th, check round
        if dist[u] != INF and dist[u] + w < dist[v]:  report "negative cycle"

Dijkstra বুদ্ধি খাটিয়ে ঠিক করত কোন edge কখন relax হবে। Bellman-Ford কোনো বুদ্ধিই খাটায় না: প্রতিটি রাউন্ডে সব edge, কোনো বিশেষ ক্রম ছাড়াই, একবার করে relax করে — আর এটি V−1 রাউন্ড চালায়। এর জন্য গ্রাফ রাখার সবচেয়ে সহজ উপায় edge list: শুধু (u, v, w) তিনটির একটি তালিকা, adjacency list-ও লাগে না।

দুটি জরুরি খুঁটিনাটি। প্রথমত, dist[u] != INF শর্তটি বাদ দেওয়া যাবে না: INF যদি একটি বড় সংখ্যা হয়, তাহলে INF + (−3) < INF হয়ে একটি পৌঁছানো-যায়-না এমন vertex থেকে মিথ্যা “উন্নতি” ছড়াবে। দ্বিতীয়ত, edge কোন ক্রমে দেখা হচ্ছে তার ওপর রাউন্ডের সংখ্যা নির্ভর করে — ভাগ্য ভালো হলে এক রাউন্ডেই সব ঠিক, খারাপ হলে V−1 রাউন্ড লাগে। নিচের উদাহরণে ইচ্ছে করেই সবচেয়ে খারাপ ক্রম নেওয়া হয়েছে।

৩ · Bellman-Ford হাতে চালানো — রাউন্ড ধরে dist টেবিল

শহরের পাঁচটি পয়েন্ট (vertex 0 থেকে 4), উৎস 0 — রাইডারের গুদাম। ওজন হলো টাকায় নিট খরচ; ঋণাত্মক মানে বোনাস খরচের চেয়ে বেশি। এই আটটি edge ঠিক এই ক্রমে প্রতিটি রাউন্ডে দেখা হবে:

লক্ষ করুন, “চূড়ান্ত হয়ে গেছে” সারিটি কী বলছে: এই উদাহরণে রাউন্ড i-এর পর ঠিক সেই vertex-গুলো সঠিক, যাদের সেরা পথে i টি বা কম edge. সাধারণভাবে নিশ্চয়তাটি হলো “অন্তত এরা সঠিক” (edge-এর ক্রম ভালো হলে অন্যরাও আগেই ঠিক হতে পারে) — পরের অংশের প্রমাণের মূল দাবি এটিই। parent অ্যারে মিলে একটি shortest-path tree তৈরি হয়: উৎস থেকে প্রতিটি vertex-এ একটি করে সেরা পথ।

Early termination — শান্ত রাউন্ডে থামা

কোনো রাউন্ডে একটিও relax সফল না হলে পরের রাউন্ডগুলোও হুবহু একই হবে — dist অ্যারে বদলায়নি, edge-ও একই, তাই ফলও একই। তাই সেখানেই থামা নিরাপদ, আর সেই “শান্ত” রাউন্ডটি নিজেই প্রমাণ যে কোনো negative cycle নেই। Edge-এর ক্রম ভালো হলে (যেমন উৎস থেকে BFS ক্রমে সাজানো) প্রায়ই অল্প কয়েক রাউন্ডেই কাজ শেষ। Best case-এ, এক রাউন্ডে সব ঠিক হয়ে দ্বিতীয়টি শান্ত হলে, মোট O(E). তবে worst case বদলায় না: উপরের মতো খারাপ ক্রমে V − 1 রাউন্ডই লাগে।

৪ · কেন V−1 রাউন্ডই যথেষ্ট — প্রমাণ আর খরচ

বিশ্ববিদ্যালয় বা চাকরির লিখিত পরীক্ষায় এই প্রমাণটি খুব প্রচলিত প্রশ্ন। ধরে নিন উৎস s থেকে পৌঁছানো যায় এমন কোনো negative cycle নেই। আমাদের দেখাতে হবে, V − 1 রাউন্ডের পর প্রতিটি vertex v-এর জন্য dist[v] = δ(s, v), যেখানে δ মানে আসল সবচেয়ে কম খরচ।

ধাপ ১ — সেরা পথ সবসময় সরল পথ

একটি simple path (সরল পথ) কোনো vertex দুবার ছোঁয় না। কোনো পথে একটি vertex দুবার এলে, মাঝের অংশটি একটি cycle. Negative cycle নেই বলে সেই cycle-এর ওজন ≥ 0; তাই cycle-টি কেটে বাদ দিলে পথের খরচ বাড়ে না। বারবার কাটতে থাকলে শেষে একটি সরল পথ পাই, যার খরচ আগেরটির চেয়ে বেশি নয়। আর V টি vertex-এর সরল পথে সর্বোচ্চ V টি vertex, তাই সর্বোচ্চ V − 1 টি edge. অর্থাৎ প্রতিটি vertex-এর এমন একটি সেরা পথ আছে, যাতে edge V − 1-এর বেশি নয়।

ধাপ ২ — dist কখনো আসল মানের নিচে নামে না

dist[v] যখনই একটি সসীম মান পায়, তখন সেটি s থেকে v পর্যন্ত কোনো একটি সত্যিকারের পথের খরচ (parent ধরে সেই পথটি পাওয়া যায়)। কোনো পথের খরচ সেরা পথের চেয়ে কম হতে পারে না, তাই সবসময় dist[v] ≥ δ(s, v). একে upper-bound property বলে: dist সবসময় আসল উত্তরের একটি ওপরের সীমা, শুধু নামতে থাকে।

ধাপ ৩ — induction

Induction-এর দাবি P(i): “রাউন্ড i-এর পর, যে vertex-এর একটি সেরা পথে i টি বা কম edge আছে, তার dist সঠিক।”

• ভিত্তি, i = 0: শুধু s নিজে, যার পথে 0 টি edge; dist[s] = 0 = δ(s, s). (Negative cycle নেই বলে δ(s, s) = 0.)
• ধাপ, i − 1 থেকে i: ধরুন v-এর সেরা পথ s → … → u → v, যাতে i টি edge. তাহলে s → … → u অংশটি u-এর একটি সেরা পথ (নইলে u পর্যন্ত আরও সস্তা পথ নিয়ে v-এর পথও সস্তা করা যেত) — এবং এতে i − 1 টি edge. Inductive hypothesis অনুযায়ী রাউন্ড i − 1-এর পরেই dist[u] = δ(s, u). রাউন্ড i-তে edge u → v অবশ্যই একবার relax হয়, তখন dist[v] ≤ δ(s, u) + w(u, v) = δ(s, v). আর ধাপ ২ বলে dist[v] ≥ δ(s, v). তাই সমান।

ধাপ ১ আর ৩ একসাথে: প্রতিটি vertex-এর সেরা পথে ≤ V − 1 edge, তাই P(V − 1) সব vertex-কে সঠিক করে। ∎ ধাপ ৩-এর মাঝখানের যুক্তি — “সেরা পথের অংশও সেরা পথ” — এর নাম optimal substructure, যা dynamic programming-এর (পর্ব ৫২) প্রধান শর্ত। বাস্তবে Bellman-Ford হলো একটি DP: d_i(v) = “সর্বোচ্চ i টি edge ব্যবহার করে v-তে যাওয়ার সেরা খরচ”, আর d_i(v) = min(d_i−1(v), min_u→v d_i−1(u) + w(u, v)). এক অ্যারেতে জায়গায় বসে হালনাগাদ করলে মান আরও আগে ঠিক হতে পারে, কিন্তু কখনো ভুল হয় না।

খরচ

V − 1 টি রাউন্ড (যাচাই নিয়ে V), প্রতিটিতে E টি edge-এর প্রতিটিতে O(1) কাজ — সময় O(V · E). জায়গা: dist আর parent মিলে O(V), edge list আলাদা O(E). Dense graph-এ (E ≈ V²) এটি O(V³), আর sparse graph-এ (E ≈ V) O(V²). তুলনায় Dijkstra O((V + E) log V) — V = E = 10⁵ হলে Bellman-Ford প্রায় 10¹⁰ ধাপ (কনটেস্টে সময়সীমার অনেক বাইরে), Dijkstra কয়েক মিলিয়ন। তাই নিয়ম: ঋণাত্মক edge না থাকলে Bellman-Ford নয়।

৫ · Negative cycle — ধরা আর খুঁজে বের করা

এবার গ্রাফ A-তে একটিমাত্র পরিবর্তন: কোম্পানি e8 = 3→2 রুটে বোনাস বাড়াল, ওজন 1 থেকে হলো −3. চক্র 2 → 1 → 4 → 3 → 2-এর ওজন এখন 2 + (−3) + 2 + (−3) = −2. রাইডার এই চক্রে যতবার ঘুরবেন, প্রতিবার ২ টাকা লাভ — অসীমবার ঘুরলে খরচ −∞. এমন গ্রাফে 1, 2, 3, 4-এর “shortest path” বলে কিছু নেই; ঠিক উত্তর হলো “negative cycle আছে” বলা। বাস্তবে এটি কোম্পানির দামের নিয়মে একটি ফাঁক, যা খুঁজে বের করাই কাজ।

পরীক্ষাটি সহজ: V − 1 রাউন্ডের পর আরও একটি (V-তম) রাউন্ড চালান। কোনো edge তখনও relax হলে, s থেকে পৌঁছানো যায় এমন একটি negative cycle আছে। দুই দিকেই প্রমাণ:

• Cycle না থাকলে V-তম রাউন্ড শান্ত: অংশ ৪ বলে তখন সব dist সঠিক, আর সঠিক মান আর কমতে পারে না (ধাপ ২)।
• Cycle থাকলে কিছু একটা বদলাবেই: ধরুন পৌঁছানো যায় এমন cycle v₀ → v₁ → … → v_k = v₀, ওজনের যোগফল < 0, অথচ কোনো edge relax হয় না। তাহলে প্রতিটি edge-এ dist[v_i] ≤ dist[v_i−1] + w_i. সব k টি অসমতা যোগ করলে দুই পাশের dist-এর যোগফল একই (cycle-এ প্রতিটি vertex একবার করে আসে), তাই কেটে যায়: 0 ≤ Σ w_i — কিন্তু Σ w_i < 0. স্ববিরোধ. (cycle পৌঁছানো যায় বলে এর সব dist সসীম, তাই যোগ-বিয়োগ বৈধ।)

“আছে” বলাই যথেষ্ট নয় — প্রায়ই cycle-টি দেখাতে হয় (কোন মুদ্রাগুলো হাতবদল করলে লাভ)। কৌশল: V-তম রাউন্ডে যে vertex x relax হয়েছে, তার parent ধরে V বার পিছিয়ে যান. x নিজে হয়তো cycle-এর বাইরে, cycle থেকে বেরোনো কোনো লেজে; কিন্তু parent-পথে V বার হাঁটলে কোনো vertex অবশ্যই পুনরাবৃত্তি হয় (pigeonhole), অর্থাৎ পথটি একটি cycle-এ ঢুকে পড়েছে — আর তারপর সেখানেই ঘুরতে থাকে। সেই y থেকে আবার parent ধরে y-তে ফেরা পর্যন্ত হাঁটলেই পুরো cycle.

এবার পুরো অ্যালগরিদম কোডে — দুটি নির্দিষ্ট গ্রাফে: A (cycle নেই) আর B (শুধু e8-এর ওজন বদলানো)। শান্ত রাউন্ড পেলে থামে, নইলে V-তম রাউন্ডের শেষ relax-করা vertex থেকে cycle বের করে।

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct Edge { int u, v; long long w; };
const long long INF = 1'000'000'000'000'000'000LL;

void bellmanFord(int n, const vector<Edge>& edges, int src) {
    vector<long long> d(n, INF); vector<int> par(n, -1);
    d[src] = 0; int x = -1;
    for (int r = 1; r <= n; ++r) {                    // n-1 rounds + 1 check round
        x = -1;
        for (auto [u, v, w] : edges)                   // never relax out of "infinity"
            if (d[u] != INF && d[u] + w < d[v]) { d[v] = d[u] + w; par[v] = u; x = v; }
        if (x == -1) {                                 // a quiet round: nothing can change any more
            cout << "no negative cycle, quiet round = " << r << "\ndist:";
            for (long long dv : d) cout << ' ' << dv;
            vector<int> path;
            for (int v = 3; v != -1; v = par[v]) path.push_back(v);
            cout << "\npath to 3:";
            for (int i = (int)path.size() - 1; i >= 0; --i) cout << ' ' << path[i];
            cout << '\n';
            return;
        }
    }
    for (int i = 0; i < n; ++i) x = par[x];           // step back n times: x is now ON the cycle
    vector<int> cyc{x};
    for (int v = par[x]; v != x; v = par[v]) cyc.push_back(v);
    cyc.push_back(x);
    reverse(cyc.begin(), cyc.end());
    cout << "negative cycle: ";
    for (size_t i = 0; i < cyc.size(); ++i) cout << (i ? " -> " : "") << cyc[i];
    cout << '\n';
}
int main() {
    vector<Edge> g = {{4,3,2}, {1,4,-3}, {2,1,2}, {0,2,4}, {0,1,7}, {0,3,8}, {2,4,6}, {3,2,1}};
    cout << "Graph A\n"; bellmanFord(5, g, 0);
    g[7].w = -3;                                       // the bonus on 3->2 grows: weight 1 becomes -3
    cout << "Graph B\n"; bellmanFord(5, g, 0);
}

Graph A
no negative cycle, quiet round = 5
dist: 0 6 4 5 3
path to 3: 0 2 1 4 3
Graph B
negative cycle: 2 -> 1 -> 4 -> 3 -> 2

INF = 10**18

def bellman_ford(n, edges, src):
    d, par = [INF] * n, [-1] * n
    d[src] = 0
    for r in range(1, n + 1):                 # n-1 rounds + 1 check round
        x = -1
        for u, v, w in edges:
            if d[u] != INF and d[u] + w < d[v]:   # never relax out of "infinity"
                d[v], par[v], x = d[u] + w, u, v
        if x == -1:                            # a quiet round: nothing can change any more
            print(f"no negative cycle, quiet round = {r}")
            print("dist:", *d)
            path, v = [], 3
            while v != -1:
                path.append(v)
                v = par[v]
            print("path to 3:", *path[::-1])
            return
    for _ in range(n):                         # step back n times: x is now ON the cycle
        x = par[x]
    cyc, v = [x], par[x]
    while v != x:
        cyc.append(v)
        v = par[v]
    cyc.append(x)
    print("negative cycle:", " -> ".join(map(str, cyc[::-1])))

g = [(4, 3, 2), (1, 4, -3), (2, 1, 2), (0, 2, 4), (0, 1, 7), (0, 3, 8), (2, 4, 6), (3, 2, 1)]
print("Graph A")
bellman_ford(5, g, 0)
g[7] = (3, 2, -3)                              # the bonus on 3->2 grows: weight 1 becomes -3
print("Graph B")
bellman_ford(5, g, 0)

Graph A
no negative cycle, quiet round = 5
dist: 0 6 4 5 3
path to 3: 0 2 1 4 3
Graph B
negative cycle: 2 -> 1 -> 4 -> 3 -> 2

৬ · SPFA — queue দিয়ে Bellman-Ford, আর তার ফাঁদ

প্রথম ডায়াগ্রামে দেখুন: রাউন্ড ৪-এ আটটি edge-এর সাতটি দেখা হয়েছে অযথা, কারণ তাদের শুরুর vertex-এর dist আগের রাউন্ড থেকে বদলায়নি। Edge u → v শুধু তখনই নতুন কিছু দিতে পারে, যখন dist[u] সম্প্রতি কমেছে। এই পর্যবেক্ষণ থেকে SPFA (Shortest Path Faster Algorithm): একটি queue-তে রাখুন শুধু সেই vertex-গুলো, যাদের dist কমেছে কিন্তু যাদের বাইরের edge এখনো দেখা হয়নি।

// SPFA: adj[u] = list of (v, w); returns false if a negative cycle is reachable from s
bool spfa(int n, const vector<vector<pair<int,long long>>>& adj, int s, vector<long long>& d) {
    d.assign(n, INF); vector<int> cnt(n, 0); vector<char> inq(n, 0);
    queue<int> q; d[s] = 0; q.push(s); inq[s] = 1;
    while (!q.empty()) {
        int u = q.front(); q.pop(); inq[u] = 0;
        for (auto [v, w] : adj[u])
            if (d[u] + w < d[v]) {
                d[v] = d[u] + w;
                if (!inq[v]) {                    // not already waiting in the queue
                    if (++cnt[v] >= n) return false;   // queued n times: negative cycle
                    q.push(v); inq[v] = 1;
                }
            }
    }
    return true;
}

এখানে queue থেকে বের হওয়া u-এর dist সবসময় সসীম, তাই আলাদা INF যাচাই লাগে না। Negative cycle ধরার নিয়ম: কোনো vertex n বার queue-তে ঢুকলে থামুন — cycle না থাকলে প্রতিটি vertex সর্বোচ্চ V − 1 বার উন্নত হতে পারে (প্রতিটি “রাউন্ড”-এ একবার)। বাস্তবের অনেক গ্রাফে, বিশেষত এলোমেলো sparse গ্রাফে, SPFA প্রায়ই Bellman-Ford-এর চেয়ে অনেক দ্রুত — অনেক সময় প্রায় O(E)-এর কাছাকাছি।

SPFA নামটি জনপ্রিয় হয় চীনে, ১৯৯৪ সালে Duan Fanding-এর একটি প্রবন্ধের পর, বিশেষ করে সেখানকার প্রতিযোগিতামূলক প্রোগ্রামিংয়ে। কিন্তু queue-ভিত্তিক এই ধারণা নতুন নয়: Edward F. Moore-এর ১৯৫৯ সালের কাজেই এর মূল রূপ ছিল, তাই পশ্চিমের বইয়ে একে প্রায়ই “queue-based Bellman-Ford” বা Bellman-Ford-Moore বলে।

৭ · সব জোড়ার shortest path — Floyd-Warshall

এ পর্যন্ত প্রশ্ন ছিল একটি উৎস থেকে — single-source shortest path. কিন্তু অনেক সময় দরকার প্রতিটি জোড়া (i, j)-এর দূরত্ব: যেমন দেশের ৬৪টি জেলা সদরের মধ্যে বাস ভাড়ার পুরো টেবিল, বা একটি কোম্পানির সব অফিসের মধ্যে নেটওয়ার্কের দেরি। এটি all-pairs shortest path (APSP). প্রতিটি vertex থেকে একবার করে Bellman-Ford চালালে O(V²E) — dense গ্রাফে O(V⁴). অনেক ভালো একটি উপায় আছে, আর তার কোড মাত্র তিনটি লুপ।

DP-র ধারণা — মাঝের vertex একে একে খুলে দেওয়া

vertex-গুলোকে নম্বর দিন 1, 2, …, V (এই অংশের গণিতে 1-based; কোডে 0-based). সংজ্ঞা দিন:

k = 0 মানে কোনো মাঝের vertex নিষেধ — শুধু সরাসরি edge: d₀[i][j] = w(i, j), না থাকলে ∞, আর d₀[i][i] = 0. এটিই গ্রাফের adjacency matrix. এবার k-তম vertex “খুলে দিলে” i থেকে j-এর সেরা পথ দুই রকম হতে পারে:

• k ব্যবহার করে না: তাহলে উত্তর আগের মতোই, d_k−1[i][j].
• k ব্যবহার করে: negative cycle নেই বলে সেরা পথটি সরল, তাই k একবারই আসে। পথ ভাঙে দুই টুকরোয় — i থেকে k, আর k থেকে j — আর দুই টুকরোর মাঝের vertex-গুলো {1, …, k − 1} থেকে। Optimal substructure বলে দুটি টুকরোই নিজেরা সেরা: d_k−1[i][k] + d_k−1[k][j].

k = V-তে সব vertex খোলা, তাই d_V হলো আসল দূরত্ব। এটিই Floyd-Warshall অ্যালগরিদম. উপমায়: ঢাকা থেকে রাজশাহী যাওয়ার সেরা ভাড়া খুঁজছেন। প্রথমে শুধু সরাসরি বাস। তারপর অনুমতি দিলেন “সিরাজগঞ্জ হয়ে যাওয়া যাবে” — প্রতিটি জোড়ার জন্য দেখলেন সিরাজগঞ্জ হয়ে সস্তা কি না। তারপর “নাটোরও চলবে” — এবার সিরাজগঞ্জ আর নাটোর দুটোই মাঝে থাকতে পারে। প্রতিটি নতুন শহর খোলার পর টেবিলটি একবার হালনাগাদ।

কেন k সবার বাইরের লুপে — আর এক matrix-এ কেন চলে

সূত্রে d_k নির্ভর করে শুধু d_k−1-এর ওপর। তাই k-এর একটি মান শেষ না করে পরের মানে যাওয়া যায় না: k বাইরে, i আর j ভেতরে. ভেতরের দুটি লুপের ক্রম (i-j না j-i) নিয়ে চিন্তা নেই। কিন্তু ভুল করে i-j-k লিখলে প্রতিটি d[i][j] একবারই হিসাব হয়, তখনকার অর্ধেক-তৈরি মান দিয়ে। ছোট উদাহরণ: শুধু তিনটি edge 0→2, 2→3, 3→1, প্রতিটির ওজন 1. আসল d[0][1] = 3 (0→2→3→1). i-j-k ক্রমে (i = 0, j = 1)-এর সময় d[0][3] তখনো ∞ (সেটি হিসাব হবে পরে, j = 3-এ), আর d[2][1]-ও ∞ (i = 2 আসবে পরে) — তাই d[0][1] চিরকাল ∞ থেকে যায়।

আর দ্বিতীয় প্রশ্ন: d_k−1 আর d_k-এর জন্য দুটি আলাদা matrix লাগার কথা, একটিতে কেন চলে? কারণ ধাপ k-তে সারি k আর কলাম k বদলায় না: d[i][k]-এর নতুন মান = min(d[i][k], d[i][k] + d[k][k]), আর d[k][k] = 0 (negative cycle না থাকলে) — তাই একই থাকে। অর্থাৎ ধাপ k-তে যেসব মান পড়া হয় (d[i][k] আর d[k][j]), সেগুলো ওই ধাপে কেউ বদলায় না। জায়গা তাই Θ(V²), Θ(V³) নয়।

#include <iomanip>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
const long long INF = 1'000'000'000'000'000'000LL;
struct Edge { int u, v; long long w; };

int main() {
    const int n = 4;
    vector<vector<long long>> d(n, vector<long long>(n, INF));
    vector<vector<int>> nxt(n, vector<int>(n, -1));
    for (int i = 0; i < n; ++i) { d[i][i] = 0; nxt[i][i] = i; }
    for (auto [u, v, w] : vector<Edge>{{0,1,3}, {0,2,8}, {1,3,1}, {2,1,5}, {3,0,2}, {3,2,-5}}) {
        d[u][v] = w; nxt[u][v] = v;
    }
    for (int k = 0; k < n; ++k)                         // k MUST be the outer loop
        for (int i = 0; i < n; ++i) {
            if (d[i][k] == INF) continue;
            for (int j = 0; j < n; ++j)
                if (d[k][j] != INF && d[i][k] + d[k][j] < d[i][j]) {
                    d[i][j] = d[i][k] + d[k][j];
                    nxt[i][j] = nxt[i][k];              // first step: same as the first step towards k
                }
        }
    bool neg = false;
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) cout << setw(4) << (d[i][j] == INF ? string("INF") : to_string(d[i][j]));
        cout << '\n';
        neg = neg || d[i][i] < 0;
    }
    cout << "negative cycle: " << (neg ? "yes" : "no") << '\n';
    int s = 0, t = 2;
    cout << "path " << s << " -> " << t << ":";
    for (int u = s; ; u = nxt[u][t]) { cout << ' ' << u; if (u == t) break; }
    cout << " (cost " << d[s][t] << ")\n";
}

   0   3  -1   4
   3   0  -4   1
   8   5   0   6
   2   0  -5   0
negative cycle: no
path 0 -> 2: 0 1 3 2 (cost -1)

INF = 10**18
n = 4
d = [[0 if i == j else INF for j in range(n)] for i in range(n)]
nxt = [[i if i == j else -1 for j in range(n)] for i in range(n)]
for u, v, w in [(0, 1, 3), (0, 2, 8), (1, 3, 1), (2, 1, 5), (3, 0, 2), (3, 2, -5)]:
    d[u][v], nxt[u][v] = w, v

for k in range(n):                            # k MUST be the outer loop
    for i in range(n):
        if d[i][k] == INF:
            continue
        for j in range(n):
            if d[k][j] != INF and d[i][k] + d[k][j] < d[i][j]:
                d[i][j] = d[i][k] + d[k][j]
                nxt[i][j] = nxt[i][k]         # first step: same as the first step towards k

for row in d:
    print("".join(f"{'INF' if x == INF else x:>4}" for x in row))
print("negative cycle:", "yes" if any(d[i][i] < 0 for i in range(n)) else "no")
s, t, path = 0, 2, [0]
while path[-1] != t:
    path.append(nxt[path[-1]][t])
print(f"path {s} -> {t}:", *path, f"(cost {d[s][t]})")

   0   3  -1   4
   3   0  -4   1
   8   5   0   6
   2   0  -5   0
negative cycle: no
path 0 -> 2: 0 1 3 2 (cost -1)

খরচ — কখন Θ(V³) ঠিক আছে

V = 100 হলে 10⁶ ধাপ — চোখের পলকে। V = 500 হলে 1.25 × 10⁸ — C++-এ সাধারণত এক সেকেন্ডের মধ্যে, কারণ ভেতরের লুপ খুব সরল আর একটি সারি ধরে ক্রমানুসারে মেমরি পড়ে, যা cache-এর জন্য চমৎকার। V = 2000 হলে 8 × 10⁹ — কয়েক সেকেন্ডের বেশি, সাধারণ কনটেস্টের সীমার বাইরে। তাই মোটা দাগের নিয়ম: V প্রায় ৫০০ পর্যন্ত Floyd-Warshall নিশ্চিন্তে; এর বেশি হলে আর গ্রাফ sparse হলে প্রতিটি vertex থেকে Dijkstra (বা ঋণাত্মক edge থাকলে Johnson) ভাবুন। Floyd-Warshall-এর আরেকটি সুবিধা হলো এটি লেখা প্রায় অসম্ভব রকম সহজ, তাই ভুলের সুযোগও কম।

৮ · Floyd-Warshall-এর আরও কাজ — negative cycle, পথ, transitive closure

কর্ণে negative cycle

d[i][i] শুরু হয় 0 থেকে। শেষে যদি d[i][i] < 0 হয়, তাহলে i থেকে বেরিয়ে i-তে ফেরার একটি পথ আছে যার খরচ ঋণাত্মক — অর্থাৎ i একটি negative cycle-এর ওপর। উল্টোটাও সত্য: i কোনো negative cycle-এ থাকলে সেই cycle-এর vertex-গুলো যখন একে একে খোলা হয়, d[i][i] ঋণাত্মক হয়ে যায়। তাই কোডে একটি লাইনই যথেষ্ট: কোনো i-তে d[i][i] < 0 আছে কি না। কোন জোড়ার দূরত্ব −∞? যদি এমন একটি k থাকে যাতে d[i][k] আর d[k][j] দুটোই সসীম এবং d[k][k] < 0 — অর্থাৎ i থেকে একটি negative cycle-এ পৌঁছে সেখান থেকে j-তে যাওয়া যায়।

পথ পুনর্গঠন — next[][]

শুধু দূরত্ব নয়, পথও চাই — যেমন ভাড়ার টেবিলের পাশে “কোন কোন শহর হয়ে”. প্রতিটি জোড়ার জন্য পুরো পথ রাখলে Θ(V³) জায়গা লাগত। কৌশল হলো path reconstruction-এর জন্য শুধু একটি সংখ্যা রাখা: next[i][j] = “i থেকে j-এর সেরা পথে i-এর পরের vertex”. শুরুতে প্রতিটি edge i → j-এর জন্য next[i][j] = j. যখন k হয়ে নতুন পথ পাওয়া যায় (i → … → k → … → j), তখন i থেকে প্রথম ধাপটি k-এর দিকের প্রথম ধাপের সমান: next[i][j] = next[i][k]. পথ বের করতে i থেকে শুরু করে বারবার next[·][j] ধরে এগোন, যতক্ষণ না j-তে পৌঁছান।

Transitive closure — শুধু “যাওয়া যায় কি না”

কখনো খরচ জানার দরকারই নেই, শুধু প্রশ্ন: i থেকে j-এ কোনো পথ আছে কি? যেমন একটি কোর্সের prerequisite-এর গ্রাফে “Data Structures না পড়ে কি Compiler Design-এ যাওয়া যায়?”, বা কোনো সফটওয়্যারে কোন module পরোক্ষভাবে কোন module-এর ওপর নির্ভর করে। সব জোড়ার এই উত্তরের টেবিলকে বলে transitive closure. Floyd-Warshall-এর min আর + বদলে দিন OR আর AND দিয়ে:

// Warshall: reach[i][j] = true if j can be reached from i (reach[i][i] = true initially)
for (int k = 0; k < n; ++k)
    for (int i = 0; i < n; ++i)
        if (reach[i][k])
            for (int j = 0; j < n; ++j)
                reach[i][j] = reach[i][j] || reach[k][j];
// faster: store each row as a bitset<N> and do  if (reach[i][k]) reach[i] |= reach[k];  --  O(V^3 / 64)

যুক্তি একই: “মাঝে শুধু {0…k} ব্যবহার করে i থেকে j-এ যাওয়া যায়” = আগেই যাওয়া যেত, অথবা i থেকে k-তে আর k থেকে j-তে যাওয়া যায়। প্রতিটি সারিকে bit-এর সারি (std::bitset) হিসেবে রাখলে ভেতরের j-লুপ একসাথে ৬৪টি করে bit সামলায়, তাই V = 2000-এর মতো আকারেও কাজ চলে। একই কাঠামো আরও অনেক “সব জোড়া”-র প্রশ্নে খাটে — যেমন minimax path (পথের সবচেয়ে বড় edge যতটা সম্ভব ছোট), যেখানে min আর + বদলে হয় min আর max.

৯ · কোন shortest-path অ্যালগরিদম কখন

এই মডিউলে এখন পর্যন্ত shortest path-এর পাঁচ-ছয়টি উপায় দেখেছেন। কনটেস্ট বা ইন্টারভিউতে সমস্যা পড়ে প্রথম কাজ হলো তিনটি প্রশ্নের উত্তর খোঁজা: ওজন কেমন (নেই, 0/1, ধনাত্মক, ঋণাত্মক)? গ্রাফে cycle আছে কি (DAG কি না)? একটি উৎস না সব জোড়া, আর V, E কত বড়?

টেবিলের একটি নীতি: সবচেয়ে নির্দিষ্ট পরিস্থিতির সবচেয়ে দ্রুত অ্যালগরিদম আগে খুঁজুন। ওজনহীন গ্রাফে Dijkstra লিখলে উত্তর ঠিক আসবে, কিন্তু অকারণে log V গুণ ধীর; DAG-এ ঋণাত্মক ওজন দেখে Bellman-Ford লিখলে O(VE) লাগবে, অথচ topological DP O(V + E)-এ একই কাজ করে। আর উল্টো ভুলটি বিপজ্জনক: ঋণাত্মক edge-এ Dijkstra — দ্রুত, কিন্তু ভুল।

১০ · AI-এর যুগে shortest path — কোড চলে, উত্তর ভুল

“Bellman-Ford লিখে দাও” — AI মুহূর্তে লিখবে, আর ছোট ধনাত্মক উদাহরণে সেটি ঠিক উত্তরও দেবে। এই অ্যালগরিদমগুলোর ভুল লুকিয়ে থাকে বিশেষ পরিস্থিতিতে: পৌঁছানো যায় না এমন vertex, negative cycle, লুপের ক্রম, overflow. আর complexity-র প্রশ্নে AI প্রায়ই SPFA-কে O(E) বলে, বা “ঋণাত্মক edge থাকলেও negative cycle না থাকলে Dijkstra চলে” — এমন আত্মবিশ্বাসী কিন্তু ভুল দাবি করে।

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

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

• একটি ছোট গ্রাফে প্রতি রাউন্ডের dist টেবিল হাতে লিখে কোডের আউটপুটের সাথে মিলিয়েছি
• Edge case চালিয়েছি: একটিমাত্র vertex, edge নেই, পৌঁছানো যায় না এমন vertex, self-loop, একই জোড়ায় দুটি edge, ওজন 0
• Negative cycle আছে এমন গ্রাফ, আর cycle-এর বাইরে লেজসহ গ্রাফ — দুটোতেই চালিয়েছি
• ছোট এলোমেলো গ্রাফে Floyd-Warshall-এর matrix আর প্রতিটি উৎস থেকে Bellman-Ford-এর উত্তর মিলিয়ে stress testing করেছি
• খুব ছোট গ্রাফে সব সরল পথ গুনে বের করা brute force উত্তরের সাথে মিলিয়েছি
• INF-এর মান, long long আর সবচেয়ে বড় সম্ভাব্য পথ-খরচ হিসাব করে overflow-এর ঝুঁকি দেখেছি