লিংক স্টেট রাউটিং — OSPF

# Dijkstra-এর শর্টেস্ট-পাথ অ্যালগরিদম — সম্পূর্ণ, সঠিক বাস্তবায়ন
import heapq

# নেটওয়ার্ক টপোলজি: রাউটারদের মধ্যে লিংক ও তাদের খরচ (OSPF-এ যেমন "cost" মেট্রিক)
graph = {
    "A": {"B": 2, "C": 5},
    "B": {"A": 2, "C": 1, "D": 4},
    "C": {"A": 5, "B": 1, "D": 1, "E": 3},
    "D": {"B": 4, "C": 1, "E": 1},
    "E": {"C": 3, "D": 1},
}

def dijkstra(graph, source):
    dist = {node: float("inf") for node in graph}
    prev = {node: None for node in graph}
    dist[source] = 0
    visited = set()
    pq = [(0, source)]
    while pq:
        d, u = heapq.heappop(pq)
        if u in visited:
            continue
        visited.add(u)
        for neighbor, weight in graph[u].items():
            new_dist = d + weight
            if new_dist < dist[neighbor]:
                dist[neighbor] = new_dist
                prev[neighbor] = u
                heapq.heappush(pq, (new_dist, neighbor))
    return dist, prev

def build_path(prev, target):
    path = []
    node = target
    while node is not None:
        path.append(node)
        node = prev[node]
    path.reverse()
    return path

source = "A"
distances, previous = dijkstra(graph, source)

print(f"'{source}' থেকে প্রতিটি রাউটারে সর্বনিম্ন-খরচের পথ —\n")
for node in graph:
    path = build_path(previous, node)
    print(f"  {source} -> {node}:  খরচ = {distances[node]:<3}  পথ = {' -> '.join(path)}")

# --- স্ব-যাচাই: hand-trace করে যাচাই করা প্রত্যাশিত মান ---
expected = {"A": 0, "B": 2, "C": 3, "D": 4, "E": 5}
assert distances == expected, f"Dijkstra-এর ফলাফল প্রত্যাশিত মানের সাথে মেলেনি! পাওয়া গেছে: {distances}"
assert build_path(previous, "E") == ["A", "B", "C", "D", "E"], "E পর্যন্ত শর্টেস্ট পাথ ভুল!"

print("\nস্ব-যাচাই পাস — লক্ষ্য করুন সরাসরি A-C লিংকের খরচ ৫ হলেও,")
print("A-B-C পথের খরচ মাত্র ৩ — তাই C-তে পৌঁছানোর প্রকৃত শর্টেস্ট পাথ B হয়ে যায়, সরাসরি লিংক দিয়ে নয়।")