LEVEL 6 · Data Structures & Algorithms

Bellman-Ford

বেলম্যান-ফোর্ড

Negative weight সহ graph-এ single-source shortest path — সব edge V−1 বার relax করে; এক extra pass-এ আরও improvement মানেই negative cycle।

also: bellman ford, bellman-ford-moore

V−1 বার কেন? যেকোনো shortest path-এ সর্বোচ্চ V−1টা edge — প্রতি pass-ে অন্তত একটার distance পাকা হয়।

for _ in range(V - 1):
    changed = False
    for u, v, w in edges:
        if dist[u] + w < dist[v]:
            dist[v] = dist[u] + w; changed = True
    if not changed: break             # আগেই থিতিয়ে এলে থামো

for u, v, w in edges:                 # V-তম pass
    if dist[u] + w < dist[v]:
        print("negative cycle")

O(VE) — Dijkstra-র চেয়ে ধীর, কিন্তু negative edge সামলায় আর negative cycle শনাক্ত করে। Distance-vector routing protocol-এর (RIP) ভিত্তিও distributed Bellman-Ford।