Shortest path-এর গণিত — Dijkstra-র প্রমাণ আর traveling salesperson

১ · Weighted graph আর দূরত্ব — সমস্যাটি নির্ভুলভাবে

বাজারঘরের ডেলিভারি রাইডার মিরপুরের গুদাম থেকে যাত্রাবাড়ীতে একটি পার্সেল নিয়ে যাবেন। মানচিত্রে সরাসরি রাস্তা আছে, কিন্তু সেটি সবসময় দ্রুততম নয়; ধানমন্ডি আর মতিঝিল ঘুরে গেলে হয়তো কম সময় লাগে। “কোন পথে সবচেয়ে কম সময়?” প্রশ্নটি সহজ শোনায়, কিন্তু উত্তর যে সত্যিই সবচেয়ে কম, তা প্রমাণ করতে হলে আগে প্রশ্নটি নির্ভুলভাবে লিখতে হয়।

পর্ব ৫৭ “গ্রাফ — সংজ্ঞা, degree আর handshake theorem”-এ graph-এর সংজ্ঞা এসেছে। এখানে আমরা সাধারণত directed graph নিয়ে কথা বলব; undirected graph-এর প্রতিটি edge {u, v}-কে দুই দিকের দুটি তীর (u, v) আর (v, u) ধরলেই সব ফল সেখানেও খাটে (তবে ঋণাত্মক weight-এর undirected edge নিজেই একটি ঋণাত্মক cycle u → v → u হয়ে যায়, তাই §২-এর ফলগুলো undirected graph-এ শুধু অঋণাত্মক weight-এর জন্য প্রয়োগ করুন)।

দুটি সূক্ষ্ম কথা। প্রথমত, সংজ্ঞায় walk নেওয়া হয়েছে (vertex পুনরাবৃত্ত হতে পারে), কারণ algorithm কোন পথ খুঁজবে তা আগে থেকে জানে না; §২-এ দেখব কখন walk-কে simple path (কোনো vertex দুবার নয়) দিয়ে বদলানো যায়। দ্বিতীয়ত, edge না থাকলে weight ∞ ধরা সুবিধাজনক। এক উৎস s থেকে সব vertex-এর দূরত্ব বের করার কাজকে বলে single-source shortest path, আর সব জোড়ার জন্য all-pairs shortest path.

ছবিতে M থেকে J-এর সরাসরি কোনো রাস্তা নেই; M → D → J পথে 9 + 20 = 29 মিনিট, কিন্তু M → D → G → T → J পথে 9 + 4 + 6 + 5 = 24 মিনিট। বেশি হাব ঘুরলেও সময় কম। পরের উপপাদ্যটি সব shortest path algorithm-এর ভিত্তি।

1. P-কে তিন টুকরো লিখি: P = P_0i · P_ij · P_jk, তাই w(P) = w(P_0i) + w(P_ij) + w(P_jk). — walk-এর weight-এর সংজ্ঞা
2. উল্টোটা ধরি: v_i থেকে v_j-এ এমন একটি walk Q আছে, যার w(Q) < w(P_ij). — contradiction-এর অনুমান
3. P_ij-এর জায়গায় Q বসাই (“কেটে জোড়া”): P′ = P_0i · Q · P_jk একটি v₀ থেকে v_k-এর walk. — দুটি walk-এর শেষ আর শুরু মেলে
4. w(P′) = w(P_0i) + w(Q) + w(P_jk) < w(P), অথচ P সবচেয়ে ছোট। বিরোধ, তাই P_ij সবচেয়ে ছোট। ∎ — ধাপ ১, ২

প্রমাণে কোথাও weight অঋণাত্মক লাগেনি, আর P′ walk হলেই চলে। শেষের কথাটি গুরুত্বপূর্ণ: “সবচেয়ে লম্বা simple path”-এ একই যুক্তি চালালে P′ simple না-ও থাকতে পারে, আর সেখানে উপপাদ্যটি সত্যিই ভাঙে (অনুশীলন ৪)।

প্রমাণ। s থেকে u-এর যেকোনো walk-এর শেষে edge (u, v) জুড়ে দিলে s থেকে v-এর একটি walk পাওয়া যায়, যার weight সেই walk-এর weight + w(u, v). তাই δ(s, v) ≤ w(walk) + w(u, v) প্রতিটি walk-এর জন্য; ডান দিকের infimum নিলে ফলটি আসে (∞ আর −∞-এর স্বাভাবিক নিয়মে)। ∎ এই triangle inequality-ই পরের অংশের relaxation-এর পেছনের যুক্তি: “u হয়ে v-তে গেলে যা লাগে, v-এর দূরত্ব তার চেয়ে বেশি হতে পারে না”।

২ · ঋণাত্মক edge আর negative cycle — কখন প্রশ্নটিই অর্থহীন

সময় বা দূরত্ব ঋণাত্মক হয় না, কিন্তু খরচ হতে পারে। ধরুন বাজারঘরের রাইডার একটি রুটে ফেরার পথে আরেকটি পার্সেল তুলে বোনাস পান, তাহলে সেই রুটের “নিট খরচ” ঋণাত্মক। এখানে একটি নতুন বিপদ আসে।

(ক)-এর প্রমাণ।

1. ধরুন s থেকে C-এর একটি vertex x-এ walk A, আর x থেকে v-তে walk B. C-কে m বার ঘুরলে walk A · C^m · B পাওয়া যায়। — walk-এ vertex পুনরাবৃত্ত হতে পারে
2. তার weight w(A) + m · w(C) + w(B). w(C) < 0, তাই m বাড়ালে এটি যত খুশি ছোট হয়। — রৈখিক রাশি, ঋণাত্মক ঢাল
3. অতএব কোনো সসীম নিম্নসীমা নেই, δ(s, v) = −∞, আর “সবচেয়ে ছোট পথ” বলে কিছু নেই। ∎

(খ)-এর প্রমাণ।

1. যেকোনো s থেকে v-এর walk-এ কোনো vertex দুবার থাকলে, দুই উপস্থিতির মাঝের অংশটি একটি cycle. — pigeonhole-এর সরল রূপ
2. সেই cycle s থেকে পৌঁছানো যায়, তাই অনুমান অনুযায়ী তার weight ≥ 0; cycle-টি কেটে দিলে walk-এর weight বাড়ে না, আর edge-সংখ্যা কমে। — অনুমান
3. বারবার কাটলে একটি simple path পাওয়া যায়, যার weight মূল walk-এর ≤. — edge-সংখ্যা কমতে কমতে থামে
4. তাই δ(s, v) = সব simple path-এর weight-এর minimum. Simple path সসীম সংখ্যক, তাই minimum অর্জিত হয়; আর simple path-এ সর্বোচ্চ n টি vertex, অর্থাৎ ≤ n − 1টি edge. ∎ — সসীম সেটের minimum থাকে

এই উপপাদ্যের (খ) অংশই Bellman–Ford-এর “n − 1 round” আর আমাদের brute force-এর (সব simple path দেখা) বৈধতার ভিত্তি। তবে brute force দ্রুত অসম্ভব হয়ে পড়ে: n = 10 vertex-এর complete graph-এ দুটি নির্দিষ্ট vertex-এর মধ্যে simple path-এর সংখ্যা ∑_k=0⁸ 8!/(8 − k)! = 109601 (মাঝের k টি vertex ক্রমসহ বাছাই, পর্ব ৩৩-এর r-permutation দিয়ে গোনা)।

৩ · Relaxation আর Dijkstra-র algorithm

সব shortest path algorithm একটি অনুমান-সারণি d রাখে: d(v) হলো এ পর্যন্ত জানা s থেকে v-এর সবচেয়ে ভালো পথের weight-এর মান। শুরুতে d(s) = 0 আর বাকি সব ∞. তারপর একটিই মৌলিক অপারেশন বারবার চলে।

প্রমাণ (relaxation-এর সংখ্যার ওপর পর্ব ১০-এর induction):

1. ভিত্তি: শুরুতে d(s) = 0 হলো খালি walk (s)-এর weight, আর বাকি সব ∞; দুটি দাবিই সত্য (খালি walk-এর weight 0, তাই δ(s, s) ≤ 0 সত্য)। — শুরুর মান
2. ধাপ: একটি relaxation শুধু d(v) বদলায়, নতুন মান d(u) + w(u, v). Induction hypothesis অনুযায়ী d(u) হলো কোনো walk W-এর weight, তাই নতুন d(v) হলো walk W · (u, v)-এর weight. — hypothesis
3. যেকোনো walk-এর weight ≥ δ(s, v) (δ হলো infimum), তাই নতুন d(v) ≥ δ(s, v). ∎ — δ-এর সংজ্ঞা

অর্থাৎ d কখনো “খুব ছোট” হয় না; algorithm-এর কাজ শুধু তাকে নামিয়ে ঠিক δ পর্যন্ত আনা। একবার d(v) = δ(s, v) হলে আর কমতে পারে না, কারণ lemma অনুযায়ী তার নিচে যাওয়া অসম্ভব।

Dijkstra-র algorithm (সব weight ≥ 0 ধরে): একটি settled সেট S রাখুন, শুরুতে খালি। প্রতি ধাপে S-এর বাইরের যে vertex u-এর d(u) সবচেয়ে ছোট, তাকে S-এ তুলুন (“settle”), তারপর u থেকে বেরোনো প্রতিটি edge relax করুন। সবাই settle হলে থামুন। সবচেয়ে ছোট d খুঁজতে বাস্তবে priority queue (heap) ব্যবহার হয়; কোড আর O((n + m) log n) বিশ্লেষণ DSA কোর্সের পর্ব ৪৩-এ আছে। নিচের stepper ছবির graph-এ M থেকে algorithm-টি হাতে চালায়।

1d(M) = 0, বাকি ∞2settle M, relax3settle D, relax4settle U, relax5settle G, relax6settle T, relax7settle J: শেষ

এবার একই হিসাব Python-এ, settled সেটের ক্রমসহ; সঙ্গে প্রতিটি গন্তব্যের জন্য সব simple path তালিকা করে brute force-এ সবচেয়ে ছোটটি মিলিয়ে দেখা হয়েছে (উপপাদ্য ২.২(খ) অনুযায়ী simple path দেখাই যথেষ্ট)। প্রথমবার চালালে ব্রাউজারে Python (Pyodide) নামতে কয়েক সেকেন্ড লাগে; পরের ব্লকগুলো দ্রুত চলে।

import heapq
E = {('M','U'):12, ('M','D'):9, ('M','G'):15, ('U','G'):8, ('D','G'):4,
     ('D','T'):11, ('G','T'):6, ('G','J'):14, ('T','J'):5, ('D','J'):20}
G = {}                                  # undirected adjacency dict
for (a, b), w in E.items():
    G.setdefault(a, {})[b] = w
    G.setdefault(b, {})[a] = w
def dijkstra(G, s):
    d, done, pq = {s: 0}, [], [(0, s)]
    while pq:
        du, u = heapq.heappop(pq)
        if u in done:
            continue                    # stale queue entry
        done.append(u)
        print(f"settle {u} d={du:2}  S={''.join(done)}")
        for v, w in G[u].items():
            if v not in done and du + w < d.get(v, float('inf')):
                d[v] = du + w           # relaxation
                heapq.heappush(pq, (d[v], v))
    return d
def all_simple_paths(G, u, t, seen):
    if u == t:
        yield 0, [t]
        return
    for v, w in G[u].items():
        if v not in seen:
            for L, p in all_simple_paths(G, v, t, seen | {v}):
                yield L + w, [u] + p
d = dijkstra(G, 'M')
for t in 'UDGTJ':
    paths = sorted(all_simple_paths(G, 'M', t, {'M'}))
    best = paths[0]
    print(t, d[t], best[0], '-'.join(best[1]), f"({len(paths)} simple paths)")

settle M d= 0  S=M
settle D d= 9  S=MD
settle U d=12  S=MDU
settle G d=13  S=MDUG
settle T d=19  S=MDUGT
settle J d=24  S=MDUGTJ
U 12 12 M-U (7 simple paths)
D 9 9 M-D (11 simple paths)
G 13 13 M-D-G (7 simple paths)
T 19 19 M-D-G-T (15 simple paths)
J 24 24 M-D-G-T-J (15 simple paths)

৪ · Dijkstra-র সঠিকতার প্রমাণ

Dijkstra-র algorithm greedy: প্রতি ধাপে সেই মুহূর্তের সবচেয়ে ছোট d-টি নিয়ে আর কখনো ফিরে দেখে না। Greedy algorithm প্রায়ই ভুল করে, তাই প্রমাণ জরুরি। প্রমাণের কেন্দ্রে একটি loop invariant (পর্ব ১৩): S-এর প্রতিটি vertex-এর d চূড়ান্ত, অর্থাৎ d(v) = δ(s, v), এই দাবি প্রতিটি ধাপে সত্য থাকে। নিচের ছবিটি মূল যুক্তি দেখায়।

প্রমাণ (S-এর আকারের ওপর induction; invariant হলো S-এর প্রতিটি v-এর জন্য d(v) = δ(s, v) সমতা)।

1. ভিত্তি: প্রথম settle হয় s, কারণ d(s) = 0 আর বাকি সব ∞. δ(s, s) = 0, কারণ খালি পথের weight 0 আর কোনো cycle-এর weight ঋণাত্মক নয়। — weight ≥ 0
2. ধাপ: ধরুন invariant এখন সত্য, আর পরের বাছাই u (S-এর বাইরে সবচেয়ে ছোট d). u-তে পৌঁছানো না গেলে δ(s, u) = ∞ = d(u) (lemma ৩.২), কাজ শেষ। তাই ধরি পৌঁছানো যায়, আর P একটি s থেকে u-এর shortest path. — induction hypothesis
3. উল্টোটা ধরি: d(u) > δ(s, u). P শুরু হয় S-এর ভেতরে (s ∈ S) আর শেষ হয় বাইরে (u ∉ S), তাই P-এ প্রথম একটি edge x → y আছে, যেখানে x ∈ S আর y ∉ S (y = u-ও হতে পারে)। — পথ কোথাও প্রথমবার সীমানা পার হয়
4. x যখন settle হয়েছিল, তখন d(x) = δ(s, x) (hypothesis), আর edge (x, y) relax হয়েছিল; তাই d(y) ≤ δ(s, x) + w(x, y). — relaxation-এর পর d কখনো বাড়ে না
5. P-এর s থেকে y পর্যন্ত অংশটি shortest (উপপাদ্য ১.২), আর তার weight δ(s, x) + w(x, y) = δ(s, y). তাই d(y) ≤ δ(s, y), আর lemma ৩.২ অনুযায়ী d(y) = δ(s, y). — optimal substructure
6. P-এর y থেকে u পর্যন্ত বাকি অংশের weight ≥ 0, তাই δ(s, y) ≤ δ(s, u). এখানেই অঋণাত্মক weight লাগে। — সব weight ≥ 0
7. মিলিয়ে: d(y) = δ(s, y) ≤ δ(s, u) < d(u). কিন্তু y ∉ S, আর u-কে বাছা হয়েছিল কারণ S-এর বাইরে d(u) সবচেয়ে ছোট, তাই d(u) ≤ d(y). বিরোধ। অতএব d(u) = δ(s, u), invariant রক্ষা পেল। ∎ — বাছাইয়ের নিয়ম

প্রমাণের প্রতিটি ধাপে কোন তথ্য লেগেছে, তা ডান পাশে লেখা। ধাপ ৬ ছাড়া অন্য কোথাও weight ≥ 0 লাগেনি (আর ধাপ ১-এ শুধু δ(s, s) = 0 নিশ্চিত করতে)। নিচের stepper ঠিক G-কে settle করার আগের মুহূর্তে যুক্তিটি সংখ্যা দিয়ে দেখায়।

1S = {M, D, U}, পরে G2ধরি P: M ⇝ G3প্রথম বাইরের y4d(y) ≤ δ(M,x) + w(x,y)5w(P) ≥ d(y) ≥ d(G)6d(G) = δ(M, G) = 13

৫ · ঋণাত্মক edge-এ Dijkstra কেন ভাঙে

প্রমাণের ধাপ ৬ বাদ দিলে কী হয়, একটি ছোট directed graph-এ দেখা যাক: s → a (2), s → b (6), b → a (−5), a → t (3). কোনো cycle নেই, তাই negative cycle-ও নেই, আর উপপাদ্য ২.২ অনুযায়ী সব দূরত্ব সংজ্ঞায়িত: δ(s, a) = 6 − 5 = 1 (পথ s → b → a), δ(s, t) = 4.

Dijkstra চালালে: s settle, d(a) = 2, d(b) = 6. সবচেয়ে ছোট a = 2, তাই a settle হয়, আর d(t) = 5. তারপর t (5), শেষে b (6). b থেকে a-তে 6 − 5 = 1 পাওয়া যায়, কিন্তু a ইতিমধ্যে settled, তাই algorithm তাকে আর ছোঁয় না। ফল d(a) = 2 আর d(t) = 5, দুটিই ভুল। প্রমাণের ভাষায়: a settle হওয়ার সময় shortest path s → b → a প্রথমবার S ছাড়ে s → b edge-এ, d(b) = 6 ≥ d(a) = 2; কিন্তু বাকি অংশ b → a-এর weight −5 < 0, তাই ধাপ ৬ ভাঙে।

একটি জনপ্রিয় “সমাধান”: সবচেয়ে ছোট weight যত, সব edge-এ ততটা (বা তার বেশি) যোগ করে weight অঋণাত্মক বানিয়ে Dijkstra চালানো। নিচের ব্লক দুটি দাবিই পরীক্ষা করে, আর Bellman–Ford-এর ফলও দেখায় (§৬-এ তার প্রমাণ)। শেষে একটি negative cycle-এর graph-এ Bellman–Ford-এর সতর্কসংকেত।

INF = float('inf')
def dijkstra(G, s):                     # textbook: a settled vertex is final
    d, S = {v: INF for v in G}, set()
    d[s] = 0
    while len(S) < len(G):
        u = min((v for v in G if v not in S), key=d.get)
        S.add(u)
        for v, w in G[u].items():
            if v not in S:
                d[v] = min(d[v], d[u] + w)
    return d
def bellman_ford(G, s):
    d = {v: INF for v in G}
    d[s] = 0
    for _ in range(len(G) - 1):         # n - 1 rounds
        for u in G:
            for v, w in G[u].items():
                d[v] = min(d[v], d[u] + w)
    bad = any(d[u] + w < d[v] for u in G for v, w in G[u].items())
    return d, bad                       # bad = negative cycle reachable
G = {'s': {'a': 2, 'b': 6}, 'a': {'t': 3}, 'b': {'a': -5}, 't': {}}
print("Dijkstra     ", dijkstra(G, 's'))
print("Bellman-Ford ", bellman_ford(G, 's'))
c = 5                                   # "fix": add 5 to every edge
H = {u: {v: w + c for v, w in G[u].items()} for u in G}
print("shifted+5    ", dijkstra(H, 's'))
K = {'s': {'a': 3}, 'a': {'b': 2}, 'b': {'c': -4}, 'c': {'a': 1}}
print("cycle a-b-c weight", 2 - 4 + 1, bellman_ford(K, 's'))

Dijkstra      {'s': 0, 'a': 2, 'b': 6, 't': 5}
Bellman-Ford  ({'s': 0, 'a': 1, 'b': 6, 't': 4}, False)
shifted+5     {'s': 0, 'a': 7, 'b': 11, 't': 15}
cycle a-b-c weight -1 ({'s': 0, 'a': 0, 'b': 3, 'c': -1}, True)

৬ · Bellman–Ford — n − 1 round আর negative cycle ধরা

Bellman–Ford কোনো greedy বাছাই করে না: প্রতিটি round-এ সব edge একবার করে relax করে, আর মোট n − 1 round চালায়। বিস্ময়ের ব্যাপার, edge-এর ক্রম যেমনই হোক, এটুকুই যথেষ্ট।

(ক)-এর প্রমাণ (i-এর ওপর induction):

1. ভিত্তি i = 0: ০-edge-এর walk শুধু (s), weight 0, আর d(s) = 0. অন্য v-তে ০-edge-এর walk নেই, দাবি শূন্যভাবে সত্য। — শুরুর মান
2. ধাপ: W একটি s থেকে v-এর walk, ≤ i + 1টি edge, শেষ edge (u, v). W-এর বাকি অংশ W′ হলো s থেকে u-এর ≤ i edge-এর walk, তাই round i-এর পর d(u) ≤ w(W′). — hypothesis
3. Round i + 1-এ edge (u, v) relax হয়, আর ততক্ষণে d(u) শুধু কমেছে; তাই তার পর d(v) ≤ d(u) + w(u, v) ≤ w(W′) + w(u, v) = w(W). ∎ — relaxation, d কখনো বাড়ে না

(খ) উপপাদ্য ২.২(খ) অনুযায়ী প্রতিটি পৌঁছানো যায় এমন v-এর একটি shortest path ≤ n − 1 edge-এর; (ক) অনুযায়ী n − 1 round-এর পর d(v) ≤ তার weight = δ(s, v), আর lemma ৩.২ অনুযায়ী d(v) ≥ δ(s, v). পৌঁছানো না গেলে d(v) = ∞ = δ(s, v). ∎

(গ)-এর প্রমাণ।

1. Negative cycle না থাকলে (খ) অনুযায়ী d = δ, আর উপপাদ্য ১.৩ অনুযায়ী প্রতিটি edge-এ δ(s, v) ≤ δ(s, u) + w(u, v); তাই কোনো edge relax করা যায় না। — triangle inequality
2. উল্টো দিক: ধরুন C = (v₀, …, v_k = v₀) একটি পৌঁছানো যায় এমন negative cycle, অথচ C-এর প্রতিটি edge-এ d(v_i) ≤ d(v_i−1) + w(v_i−1, v_i). (C পৌঁছানো যায় বলে n − 1 round-এর পর C-এর সব d সসীম।) — contradiction-এর অনুমান
3. i = 1 থেকে k পর্যন্ত যোগ করলে বাঁ দিকে ∑d(v_i), ডান দিকে ∑d(v_i−1) + w(C). Cycle বলে দুটি ∑ একই সংখ্যাগুলোর যোগ, তাই কেটে যায়: 0 ≤ w(C). — যোগফলে প্রতিটি vertex একবার করে
4. কিন্তু w(C) < 0. বিরোধ, তাই C-এর অন্তত একটি edge এখনো relax করা যায়। ∎

নিচের stepper §৫-এর শেষ graph-এ (s → a 3, a → b 2, b → c −4, c → a 1; n = 4) round গুলো দেখায়। প্রতিটি round-এ edge-এর ক্রম s→a, a→b, b→c, c→a.

1d(s) = 0, বাকি ∞2round 13round 24round 3 = n − 15যাচাই: আরেকবার দেখা

খরচ: n − 1 round, প্রতিটিতে m টি edge, মোট O(nm); Dijkstra-র চেয়ে ধীর, কিন্তু ঋণাত্মক weight সামলায়। Network routing-এর distance vector protocol একই relaxation-এর ওপর দাঁড়িয়ে (Computer Networks কোর্সের পর্ব ২৩), আর বিস্তারিত কোড DSA কোর্সের পর্ব ৪৪-এ।

৭ · DAG-এ এক পাস, আর Floyd–Warshall-এর recurrence

DAG-এ shortest path. Graph-এ কোনো directed cycle না থাকলে (একটি DAG) negative cycle-এর প্রশ্নই ওঠে না, ঋণাত্মক weight থাকলেও। পর্ব ৫৬-এ দেখেছেন প্রতিটি DAG-এর একটি topological ক্রম আছে: v₁, …, v_n, যাতে প্রতিটি edge সামনের দিকে যায়। এই ক্রমে vertex নিয়ে প্রতিটির বেরোনো edge একবার relax করলেই হয়।

1. j-এর ওপর strong induction (পর্ব ১১)। j = 1: d(s) = 0 = δ(s, s), কারণ DAG-এ কোনো cycle নেই। — ভিত্তি
2. ধরুন v_j পৌঁছানো যায়, আর P একটি shortest path, শেষ edge (v_i, v_j). Topological ক্রমে i < j, তাই v_i আগে প্রক্রিয়া হয়েছে, তখন d(v_i) = δ(s, v_i) (hypothesis), আর (v_i, v_j) relax হয়েছে। — সব edge সামনের দিকে
3. তাই d(v_j) ≤ δ(s, v_i) + w(v_i, v_j) = δ(s, v_j) (উপপাদ্য ১.২); lemma ৩.২ উল্টো অসমতা দেয়। ∎

একটি হাতের হিসাব। ক্রম A, B, C, D, E; edge A→B 3, A→C 6, B→C −2, B→D 5, C→D 1, C→E 4, D→E −3. A প্রক্রিয়ার পর B = 3, C = 6. B-এর পর C = min(6, 3 − 2) = 1, D = 8. C-এর পর D = min(8, 1 + 1) = 2, E = 5. D-এর পর E = min(5, 2 − 3) = −1. ফল A 0, B 3, C 1, D 2, E −1, খরচ O(n + m) (scratch-এ মেলানো)। Weight-এর চিহ্ন উল্টে দিলে একই পদ্ধতি DAG-এ সবচেয়ে লম্বা পথ দেয়, যা প্রকল্পের critical path হিসাবের ভিত্তি (DSA কোর্সের পর্ব ৪২)।

সব জোড়ার জন্য: Floyd–Warshall. পর্ব ৫৪-এ Warshall-এর algorithm “শুধু 1..k-কে মাঝের স্টপ ধরে i থেকে j-তে যাওয়া যায়?” প্রশ্নের উত্তর k বাড়িয়ে বাড়িয়ে বের করেছে। ∨ আর ∧-এর জায়গায় min আর + বসালেই Floyd–Warshall.

প্রমাণ। উপপাদ্য ২.২(খ) অনুযায়ী একটি simple shortest path P নেওয়া যায় (মাঝের vertex {1..k}-এ সীমিত রেখেও একই কাটার যুক্তি চলে)। দুটি ক্ষেত্র। k যদি P-এর মাঝের vertex না হয়, তাহলে P-এর সব মাঝের vertex {1..k − 1}-এ, তাই w(P) = D^(k−1)[i][j]. k যদি মাঝে থাকে, simple বলে ঠিক একবার; P-কে k-তে কাটলে দুটি টুকরো, যাদের মাঝের vertex {1..k − 1}-এ, আর optimal substructure অনুযায়ী দুটিই সবচেয়ে ছোট, তাই w(P) = D^(k−1)[i][k] + D^(k−1)[k][j]. দুটি রাশিই কোনো বৈধ walk-এর weight, তাই সবচেয়ে ছোট মানটি সঠিক। ∎ Negative cycle থাকলে কোনো D[i][i] শেষে ঋণাত্মক হয়, এভাবেই তা ধরা যায় (অনুশীলন ৩)। n = |V| বার k বাড়ে, প্রতিবার n²টি ঘর: মোট Θ(n³), Warshall-এর মতোই।

নিচের ব্লক দুটি উপপাদ্য এলোমেলো ছোট graph-এ brute force-এর বিরুদ্ধে পরীক্ষা করে। DAG-এ edge শুধু ছোট থেকে বড় নম্বরে, তাই 0..n−1 নিজেই topological ক্রম, আর weight −5 থেকে 9. Floyd–Warshall-এর জন্য পেছনের দিকের edge যোগ করা হয়েছে, কিন্তু weight ≥ 25, যাতে কোনো negative cycle না হয় (n ≤ 6-এ সামনের দিকের অংশ সর্বোচ্চ −25 কমাতে পারে)।

import random
from itertools import combinations, permutations, product
INF = float('inf')
random.seed(61)
def brute(n, W, i, j):                  # min over every simple path i -> j
    best = W[i][j] if i != j else 0
    others = [k for k in range(n) if k not in (i, j)]
    for r in range(1, len(others) + 1):
        for mid in permutations(others, r):
            best = min(best, sum(W[a][b] for a, b in zip((i, *mid), (*mid, j))))
    return best
def dag_sp(n, W, s):                    # 0..n-1 is already a topological order
    d = [INF] * n; d[s] = 0
    for u, v in combinations(range(s, n), 2):   # edges u -> v, u in order
        d[v] = min(d[v], d[u] + W[u][v])
    return d
def floyd_warshall(n, W):
    D = [[0 if i == j else W[i][j] for j in range(n)] for i in range(n)]
    for k in range(n):                  # now k may be an interior vertex
        for i, j in product(range(n), repeat=2):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])
    return D
ok_dag = ok_fw = 0
for trial in range(200):
    n = random.randint(3, 6)
    W = [[INF] * n for _ in range(n)]
    for i, j in permutations(range(n), 2):   # i < j: DAG edge, may be negative
        if i < j and random.random() < 0.6: W[i][j] = random.randint(-5, 9)
    ok_dag += all(dag_sp(n, W, 0)[j] == brute(n, W, 0, j) for j in range(n))
    for i, j in permutations(range(n), 2):   # back edges >= 25: no negative cycle
        if i > j and random.random() < 0.4: W[i][j] = random.randint(25, 30)
    D = floyd_warshall(n, W)
    ok_fw += all(D[i][j] == brute(n, W, i, j) for i, j in product(range(n), repeat=2))
print("DAG order DP == brute force:", ok_dag, "/ 200")
print("Floyd-Warshall == brute force:", ok_fw, "/ 200")

DAG order DP == brute force: 200 / 200
Floyd-Warshall == brute force: 200 / 200

একটি পরীক্ষার অঙ্ক। Vertex 1..4, edge 1→2 4, 1→4 9, 2→3 −2, 2→4 7, 3→4 1, 3→1 5, 4→2 3. D⁽⁰⁾-এ 2 থেকে 1-এ কোনো edge নেই (∞). k = 3 খোলার পর 2 → 3 → 1 = −2 + 5 = 3 আর 2 → 3 → 4 = −2 + 1 = −1 পাওয়া যায়; k = 4 খোলার পর 3 → 4 → 2 = 1 + 3 = 4 (আগের সেরা 3 → 1 → 2 = 9-এর চেয়ে ছোট)। চূড়ান্ত matrix-এর সারি: 1: (0, 4, 2, 3); 2: (3, 0, −2, −1); 3: (5, 4, 0, 1); 4: (6, 3, 1, 0). কর্ণে সব 0, তাই negative cycle নেই (প্রতিটি D^(k) scratch-এ মেলানো)।

৮ · Traveling salesperson — গণনা, কঠিনতা আর 2-approximation

বাজারঘরের একজন রাইডার সকালে গুদাম থেকে বেরিয়ে n − 1টি হাবে একবার করে পার্সেল দিয়ে গুদামে ফিরবেন। কোন ক্রমে গেলে মোট সময় সবচেয়ে কম? এটি shortest path-এর মতো শোনায়, কিন্তু একটি শর্ত সব বদলে দেয়: প্রতিটি হাবে ঠিক একবার।

কয়টি tour? শহরগুলোর একটি ক্রম (permutation) একটি tour দেয়। n!টি ক্রমের মধ্যে কোন শহর থেকে শুরু (n রকম) আর কোন দিকে ঘোরা (২ রকম) tour বদলায় না, আর n ≥ 3-এ এই 2n টি ক্রম সব আলাদা। তাই পর্ব ৩১-এর ভাগের নিয়ম অনুযায়ী symmetric tour-এর সংখ্যা

n! / (2n) = (n − 1)! / 2

n = 5-এ 12, n = 10-এ 181440, n = 20-এ প্রায় 6.08 × 10¹⁶. সব tour দেখা (brute force) ছোট n-এই থেমে যায়। Dynamic programming দিয়ে O(n² 2ⁿ) সময়ে করা যায় (Held–Karp, ১৯৬২), যা এখনো exponential.

কঠিনতা। “দূরত্ব ≤ L এমন tour আছে কি?” প্রশ্নটি NP-complete: সব weight 1 আর অ-edge-এর weight 2 দিলে, দৈর্ঘ্য n-এর tour আছে কি না মানে graph-এ Hamilton cycle আছে কি না, আর Hamilton cycle প্রশ্নটি Richard Karp-এর ১৯৭২ সালের বিখ্যাত তালিকায় NP-complete হিসেবে আছে বলে জানা যায় (পর্ব ৬০)। তাই সবচেয়ে ছোট tour খোঁজা NP-hard: P = NP প্রমাণ না হলে কোনো polynomial-time algorithm সব ক্ষেত্রে সঠিক উত্তর দেয় না বলে বিশ্বাস করা হয়। DSA কোর্সের পর্ব ৬৪-এ reduction-এর ভাষা আছে।

তাহলে আশা কোথায়? নিখুঁত উত্তর না পেলেও প্রমাণিত-ভাবে “কাছাকাছি” উত্তর। এখানে পর্ব ৬৭ “Spanning tree — DFS/BFS, minimum spanning tree আর Kirchhoff-এর গণনা”-এর minimum spanning tree (MST) কাজে আসে: সব vertex জোড়া লাগানো, cycle-হীন, সবচেয়ে কম মোট weight-এর edge-সেট। MST দ্রুত বের করা যায় (Prim বা Kruskal, DSA কোর্সের পর্ব ৪৫)।

প্রমাণের রূপরেখা।

1. (ক) সবচেয়ে ছোট tour থেকে যেকোনো একটি edge বাদ দিলে একটি Hamilton path থাকে, যা সব শহরকে জোড়ে আর cycle-হীন, অর্থাৎ একটি spanning tree. তার weight ≤ OPT (বাদ দেওয়া edge ≥ 0), আর MST সব spanning tree-র মধ্যে সবচেয়ে হালকা, তাই w(T) ≤ OPT. — D ≥ 0
2. (খ) T-এর প্রতিটি edge দুবার নিলে (যাওয়া আর ফেরা, DFS-এর মতো) একটি closed walk পাওয়া যায়, যা প্রতিটি শহর অন্তত একবার ছোঁয়, দৈর্ঘ্য ঠিক 2 · w(T). — প্রতিটি tree edge-এ একবার নামা, একবার ওঠা
3. Walk-এ আগে দেখা শহর এলে তা বাদ দিয়ে সরাসরি পরের নতুন শহরে যান; একে বলে shortcut নেওয়া। Triangle inequality অনুযায়ী D(a, c) ≤ D(a, b) + D(b, c), তাই প্রতিটি shortcut দৈর্ঘ্য বাড়ায় না। — metric শর্ত এখানেই
4. ফলে tour-এর দৈর্ঘ্য ≤ 2 · w(T) ≤ 2 · OPT. ∎ — ধাপ ১, ২, ৩

এমন algorithm-কে বলে 2-approximation: ফল কখনো সেরা উত্তরের দ্বিগুণের বেশি নয়। Triangle inequality ছাড়া এমন কোনো ধ্রুব নিশ্চয়তা পাওয়া যায় না, যদি না P = NP (Sahni ও Gonzalez, ১৯৭৬, বলে উল্লেখ করা হয়)। বিস্তারিত DSA কোর্সের পর্ব ৬৬-এ।

Nearest neighbour heuristic. সবচেয়ে সহজ greedy নিয়ম: যেখানে আছেন, তার সবচেয়ে কাছের না-দেখা শহরে যান। নিচের ব্লক এলোমেলো সমতল বিন্দুতে (Euclidean দূরত্ব, যা metric) brute force-এর OPT, nearest neighbour-এর ফল আর MST-এর weight তুলনা করে, আর প্রতিটি ক্ষেত্রে w(T) ≤ OPT ≤ 2 · w(T) যাচাই করে (OPT ≤ 2 · w(T) আসে উপপাদ্য ৮.২(খ) থেকে)। শেষে একটি metric নয় এমন ৪-শহরের ফাঁদ।

import random
from itertools import permutations
from math import dist, factorial
random.seed(2026)
def tour_len(D, t):
    return sum(D[a][b] for a, b in zip(t, t[1:] + t[:1]))
def brute_tsp(D):                       # fix city 0, try (n-1)! orders
    n = len(D)
    return min(tour_len(D, (0,) + p) for p in permutations(range(1, n)))
def nearest_neighbour(D):
    t, left = [0], set(range(1, len(D)))
    while left:
        nxt = min(left, key=lambda v: D[t[-1]][v])
        t.append(nxt); left.remove(nxt)
    return tour_len(D, tuple(t))
def mst_weight(D):                      # Prim, O(n^2)
    n, inside, w = len(D), {0}, 0
    while len(inside) < n:
        c, v = min((D[u][v], v) for u in inside for v in range(n) if v not in inside)
        inside.add(v); w += c
    return w
for n in (5, 7, 9):
    worst = 1.0
    for _ in range(6):
        P = [(random.randint(0, 99), random.randint(0, 99)) for _ in range(n)]
        D = [[dist(p, q) for q in P] for p in P]
        opt, nn, m = brute_tsp(D), nearest_neighbour(D), mst_weight(D)
        assert m <= opt <= 2 * m        # MST <= OPT <= 2 MST (metric)
        worst = max(worst, nn / opt)
    print(f"n={n}: {factorial(n-1)//2} tours, worst NN/OPT = {worst:.3f}")
M = 1000                                # non-metric trap for the greedy rule
D = [[0, 1, 2, M], [1, 0, 1, 2], [2, 1, 0, 1], [M, 2, 1, 0]]
print("trap: NN =", nearest_neighbour(D), " OPT =", brute_tsp(D))

n=5: 12 tours, worst NN/OPT = 1.095
n=7: 360 tours, worst NN/OPT = 1.071
n=9: 20160 tours, worst NN/OPT = 1.194
trap: NN = 1003  OPT = 6

৯ · এক নজরে তুলনা, আরও গভীরে আর পরীক্ষার প্রশ্ন

১০ · AI-এর যুগে — shortest path-এর প্রমাণ আর হিসাব যাচাই

Graph algorithm-এর প্রশ্নে AI সহকারী সাধারণত কোড ভালো লেখে, কিন্তু প্রমাণে আর শর্তে আত্মবিশ্বাসী ভুল করে। কয়েকটি নিয়মিত ভুল আর ধরার উপায়:

AI-এর উত্তর হাতে পেলে — যাচাইয়ের চেকলিস্ট

• উপপাদ্যে weight আর negative cycle-এর শর্ত স্পষ্ট লেখা আছে
• প্রমাণের যে ধাপে weight ≥ 0 লাগে, তা খুঁজে পেয়েছি
• Induction-এর ভিত্তি আর hypothesis আলাদা করে লেখা, কোনো ধাপ বৃত্তাকার নয়
• ছোট graph-এ brute force (সব simple path) দিয়ে উত্তর মিলিয়েছি
• শর্ত ভাঙে এমন একটি পাল্টা-উদাহরণে algorithm চালিয়ে দেখেছি
• গণনার সূত্র (যেমন tour-এর সংখ্যা) n = 4 বা 5-এ তালিকা করে মিলিয়েছি
• উদ্ধৃত নাম, সাল আর উৎস বিশ্বস্ত পাঠ্যবইয়ে মিলিয়েছি

Shortest path-এর সুবিধা হলো ছোট graph-এ সব simple path গুনে ফেলা যায়, তাই যেকোনো দাবি মিনিটের মধ্যে পরীক্ষা করা চলে। ভুল প্রমাণ সাধারণত একটি শর্ত চুপচাপ বাদ দেয়; সেই শর্ত ভাঙা একটি ৩-৪ vertex-এর graph প্রায় সবসময় ভুলটি ধরিয়ে দেয়।