ডাইজকস্ট্রা ও বেলম্যান-ফোর্ড শর্টেস্ট পাথ

import heapq

def dijkstra(adj, source, n):
    # প্রমিত Dijkstra's: একবার একটি ভার্টেক্স "ফাইনালাইজড" (visited) হয়ে গেলে
    # তার দূরত্ব আর পুনর্বিবেচনা করা হয় না -- এটিই নন-নেগেটিভ-ওয়েট অনুমানের উপর নির্ভরশীল অংশ
    dist = {v: float("inf") for v in range(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, []):
            if v in visited:
                continue
            nd = d + w
            if nd < dist[v]:
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

def bellman_ford(edges, source, n):
    dist = {v: float("inf") for v in range(n)}
    dist[source] = 0
    for _ in range(n - 1):
        updated = False
        for u, v, w in edges:
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
                updated = True
        if not updated:
            break
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            raise ValueError("নেগেটিভ-ওয়েট সাইকেল ডিটেক্টেড -- শর্টেস্ট পাথ সংজ্ঞায়িত নয়")
    return dist

def brute_force_shortest(adj, source, target):
    # সম্পূর্ণ স্বাধীন: সোর্স থেকে টার্গেটে সব সিম্পল পাথের খরচ গণনা করে সবচেয়ে ছোটটি বের করা
    best = [float("inf")]
    def explore(u, visited, cost):
        if u == target:
            best[0] = min(best[0], cost)
        for v, w in adj.get(u, []):
            if v not in visited:
                visited.add(v)
                explore(v, visited, cost + w)
                visited.remove(v)
    explore(source, {source}, 0)
    return best[0]

# ভার্টেক্স: 0=A (সোর্স), 1=B, 2=C
adj = {0: [(1, 1), (2, 4)], 1: [], 2: [(1, -10)]}
edge_list = [(0, 1, 1), (0, 2, 4), (2, 1, -10)]
n = 3
names = {0: "A", 1: "B", 2: "C"}

dist_dijkstra = dijkstra(adj, 0, n)
dist_bf = bellman_ford(edge_list, 0, n)
true_dist_B = brute_force_shortest(adj, 0, 1)

print("ভার্টেক্স | Dijkstra's dist | Bellman-Ford dist | ব্রুট-ফোর্স সত্য দূরত্ব")
for v in range(n):
    truth = brute_force_shortest(adj, 0, v) if v != 0 else 0
    print(f"  {names[v]}      | {dist_dijkstra[v]:>15} | {dist_bf[v]:>18} | {truth}")

print(f"\nA থেকে B-এর প্রকৃত শর্টেস্ট দূরত্ব (ব্রুট-ফোর্স): {true_dist_B}")
print(f"Dijkstra's-এর গণনা: {dist_dijkstra[1]}  -> সঠিক? {dist_dijkstra[1] == true_dist_B}")
print(f"Bellman-Ford-এর গণনা: {dist_bf[1]}  -> সঠিক? {dist_bf[1] == true_dist_B}")

assert dist_dijkstra[1] != true_dist_B, "প্রত্যাশা ছিল Dijkstra's ভুল উত্তর দেবে এই গ্রাফে!"
assert dist_bf[1] == true_dist_B, "Bellman-Ford-এর সঠিক উত্তর দেওয়ার কথা ছিল!"
print("\nনিশ্চিত হলো: এই নেগেটিভ-এজ গ্রাফে Dijkstra's ভুল, Bellman-Ford সঠিক।")