ফ্লয়েড-ওয়ারশাল অল-পেয়ার্স শর্টেস্ট পাথ

১ · রিকারেন্স ও অপটিমাল সাবস্ট্রাকচার

ধরি ভার্টেক্সগুলো $1$ থেকে $n$ পর্যন্ত নাম্বার করা আছে। $D_k[i][j]$ সংজ্ঞায়িত করি "$i$ থেকে $j$-এ যাওয়ার শর্টেস্ট পাথের দৈর্ঘ্য, যেখানে শুধুমাত্র $\{1, \ldots, k\}$ সেটের ভার্টেক্সগুলোকে ইন্টারমিডিয়েট (মাঝপথের) ভার্টেক্স হিসেবে ব্যবহারের অনুমতি আছে" হিসেবে। মূল অন্তর্দৃষ্টি: $k=0$ থেকে $k=n$ পর্যন্ত ধাপে ধাপে "ইন্টারমিডিয়েট-ভার্টেক্স-বাজেট" বাড়াতে থাকলে, প্রতিটি ধাপে হয় ভার্টেক্স $k$ ব্যবহার করা লাভজনক, নয়তো নয়:

$$D_k[i][j] = \min\bigl(D_{k-1}[i][j], \; D_{k-1}[i][k] + D_{k-1}[k][j]\bigr)$$

এই রিকারেন্সের প্রতিটি পদ ব্যাখ্যা: প্রথম পদ $D_{k-1}[i][j]$ মানে "$k$ ব্যবহার না করেই যা পাওয়া যায়" (আগের সাবপ্রবলেম থেকে সরাসরি নেওয়া অপটিমাল সমাধান), দ্বিতীয় পদ $D_{k-1}[i][k] + D_{k-1}[k][j]$ মানে "$i$ থেকে $k$ পর্যন্ত (শুধু $\{1,\ldots,k-1\}$ ব্যবহার করে) তারপর $k$ থেকে $j$ পর্যন্ত (একইভাবে)" — এই দুটোর মধ্যে ছোটটাই $D_k[i][j]$। এটি অপটিমাল সাবস্ট্রাকচারের একটি প্রত্যক্ষ উদাহরণ: অপটিমাল পাথ হয় $k$ ব্যবহার করে অথবা করে না, এবং উভয় ক্ষেত্রেই বাকি অংশ নিজেই অপটিমাল হতে হবে (নাহলে সেই অংশ প্রতিস্থাপন করে আরও ছোট সম্পূর্ণ পাথ পাওয়া যেত)। বেস কেস $D_0[i][j]$ হলো এজ ওয়েট $w(i,j)$ (এজ না থাকলে $\infty$), এবং $D_0[i][i]=0$।

যেহেতু প্রতিটি $D_k$ টেবিল $n \times n$ এবং প্রতিটি এন্ট্রি $O(1)$ সময়ে আপডেট হয়, এবং $k$ মোট $n$ বার চলে, মোট কমপ্লেক্সিটি $\Theta(n \cdot n^2) = \Theta(n^3) = \Theta(V^3)$। প্রতিটি $D_k$ টেবিল শুধু $D_{k-1}$-এর উপর নির্ভর করে বলে, ইমপ্লিমেন্টেশনে একটি একক 2D অ্যারে in-place আপডেট করলেই চলে (আলাদা $n$টি টেবিল রাখার দরকার নেই)।

২ · ইমপ্লিমেন্টেশন ও প্রতিটি সোর্স থেকে Dijkstra's দিয়ে ক্রস-ভেরিফিকেশন

যেহেতু এই টেস্ট গ্রাফে কোনো নেগেটিভ এজ নেই, Dijkstra's (L33-এর প্রমিত, সঠিক ইমপ্লিমেন্টেশন) প্রতিটি সোর্স থেকে নিরাপদে ব্যবহার করা যায়। যদি ফ্লয়েড-ওয়ারশালের বাগ থাকত (রিকারেন্স ভুল প্রয়োগ, ইন্ডেক্সিং ভুল ইত্যাদি), এই দুটি সম্পূর্ণ ভিন্ন অ্যালগরিদমিক কৌশলের ফলাফল আলাদা হয়ে যেত — তাই এই ক্রস-চেক একটি জেনুইন সঠিকতা যাচাই।

import heapq

INF = float("inf")

def floyd_warshall(n, edges):
    dist = [[INF] * n for _ in range(n)]
    for i in range(n):
        dist[i][i] = 0
    for u, v, w in edges:
        if w < dist[u][v]:
            dist[u][v] = w
    for k in range(n):
        for i in range(n):
            if dist[i][k] == INF:
                continue
            for j in range(n):
                new_len = dist[i][k] + dist[k][j]
                if new_len < dist[i][j]:
                    dist[i][j] = new_len
    return dist

def dijkstra(adj, source, n):
    dist = [INF] * n
    dist[source] = 0
    visited = set()
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for v, w in adj.get(u, []):
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

# একটি নন-নেগেটিভ-ওয়েট ডাইরেক্টেড গ্রাফ, ৬টি ভার্টেক্স, কিছু জোড়ার মধ্যে কোনো সরাসরি পথ নেই
n = 6
edges = [
    (0, 1, 4), (0, 2, 1),
    (1, 3, 1), (1, 2, 2),
    (2, 1, 1), (2, 3, 5),
    (3, 4, 3),
    (4, 5, 2),
    (5, 3, 1),
    (2, 5, 8),
]
adj = {}
for u, v, w in edges:
    adj.setdefault(u, []).append((v, w))

fw_dist = floyd_warshall(n, edges)

dijkstra_dist = [dijkstra(adj, s, n) for s in range(n)]

print("ফ্লয়েড-ওয়ারশাল বনাম প্রতিটি সোর্স থেকে Dijkstra's:")
all_agree = True
for i in range(n):
    for j in range(n):
        a, b = fw_dist[i][j], dijkstra_dist[i][j]
        if a != b:
            all_agree = False
            print(f"  পার্থক্য! dist[{i}][{j}]: FW={a}, Dijkstra={b}")

print(f"\nদুই পদ্ধতির সম্পূর্ণ ডিস্ট্যান্স ম্যাট্রিক্স একমত: {all_agree}")
assert all_agree, "ফ্লয়েড-ওয়ারশাল ও Dijkstra's-এর ফলাফল ভিন্ন -- একটিতে বাগ আছে!"

print("\nনমুনা সারি (সোর্স 0 থেকে সব ভার্টেক্সে দূরত্ব):")
print("  ফ্লয়েড-ওয়ারশাল:", fw_dist[0])
print("  Dijkstra's:      ", dijkstra_dist[0])