خوارزمية Bellman-Ford

المشكلة: ماذا لو كانت الأوزان سالبة؟

تعلّمت أن خوارزمية Dijkstra تجد أقصر مسار برسم بياني موزون — لكنها تفشل إن وُجد ضلع بوزن سالب. السبب: Dijkstra تفترض أن أرخص تكلفة معروفة لعقدة معالَجة نهائية ولن تتحسّن لاحقًا، وهذا الافتراض ينهار مع أوزان سالبة (مسار طويل قد يصبح فجأة أرخص بسبب ضلع سالب يُكتشف متأخّرًا). خوارزمية Bellman-Ford تحلّ هذا: أبطأ من Dijkstra، لكنها تتعامل مع الأوزان السالبة بشكل صحيح، وتكتشف أيضًا وجود دورة سالبة (Negative Cycle) إن وُجدت.

الفكرة الأساسية: استرخاء كل الأضلاع مرارًا

بدل معالجة العقد بترتيب ذكي (كما تفعل Dijkstra بالكومة)، تمرّ Bellman-Ford على كل ضلع بالرسم البياني وتحاول "استرخاءه" (Relaxation: هل المسار عبر هذا الضلع أرخص من أفضل مسار معروف حاليًا؟) — وتكرّر هذا V-1 مرة، حيث V عدد العقد.

لماذا V-1 مرة بالضبط؟ أي أقصر مسار بسيط (بلا تكرار عقدة) بين عقدتين لا يمكن أن يحوي أكثر من V-1 ضلع. فبعد V-1 جولة استرخاء كاملة، كل المسافات مضمونة أنها وصلت لقيمتها النهائية الصحيحة (بافتراض عدم وجود دورة سالبة).

def bellman_ford(graph, edges, num_nodes, start):
    # edges: قائمة [(u, v, weight), ...]
    distances = {node: float("inf") for node in graph}
    distances[start] = 0

    # استرخاء كل الأضلاع V-1 مرة
    for _ in range(num_nodes - 1):
        for u, v, weight in edges:
            if distances[u] != float("inf") and distances[u] + weight < distances[v]:
                distances[v] = distances[u] + weight

    # جولة إضافية لكشف دورة سالبة
    for u, v, weight in edges:
        if distances[u] != float("inf") and distances[u] + weight < distances[v]:
            raise ValueError("الرسم البياني يحوي دورة سالبة يمكن الوصول لها من المصدر")

    return distances


nodes = ["A", "B", "C", "D"]
edges = [("A", "B", 4), ("A", "C", 5), ("B", "D", -3), ("C", "D", 2)]
graph = {n: [] for n in nodes}

print(bellman_ford(graph, edges, len(nodes), "A"))
# {'A': 0, 'B': 4, 'C': 5, 'D': 1}  → المسار A→B→D (4-3=1) أرخص من A→C→D (5+2=7)

💡 لاحظ أن الاسترخاء هنا يمرّ على قائمة الأضلاع مباشرة، لا على جيران عقدة معالَجة كما في Dijkstra — لهذا لا نحتاج طابور أولويّة (Heap) هنا إطلاقًا.

كشف الدورة السالبة

لو استمرّت جولة استرخاء إضافية (بعد الـ V-1 جولة) بتحسين أي مسافة، فهذا يعني وجود دورة سالبة يمكن الوصول لها من نقطة البداية — مسار يمكن تكراره لتقليل التكلفة إلى ما لا نهاية، فلا يوجد "أقصر مسار" حقيقي أصلًا في هذه الحالة.

التعقيد

Bellman-Ford أبطأ بوضوح (خصوصًا برسم كثيف الأضلاع)، لذا القاعدة العملية: استخدم Dijkstra افتراضيًا، وانتقل لـ Bellman-Ford فقط إن كانت الأوزان قد تكون سالبة أو تحتاج كشف دورات سالبة.

التطبيقات الحقيقية

• بروتوكولات توجيه الشبكات: RIP (Routing Information Protocol) يعتمد على مبدأ Distance-Vector القريب من فكرة Bellman-Ford.
• كشف فرص المراجحة (Arbitrage) في أسواق صرف العملات: بتحويل أسعار الصرف لأوزان سالبة (عبر اللوغاريتم)، تصبح "دورة سالبة" في الرسم البياني تعني فرصة ربح من التحويل الدائري بين عملات.
• أي مسألة تحتاج أقصر مسار مع احتمال وجود تكاليف سالبة (خصم، استرداد).

أخطاء شائعة

• نسيان الجولة الإضافية لكشف الدورة السالبة — تجاهلها يعني قبول نتائج قد تكون خاطئة تمامًا بصمت لو وُجدت دورة سالبة فعلًا.
• استخدام Bellman-Ford دائمًا "للأمان" حتى مع رسوم كبيرة بأوزان موجبة فقط — إهدار أداء غير مبرَّر؛ Dijkstra أسرع بكثير هنا وتكفي تمامًا.
• الخلط بين "دورة سالبة" و"ضلع سالب واحد" — ضلع سالب مفرد لا مشكلة فيه إطلاقًا طالما لا يشكّل مع أضلاع أخرى دورة مجموع أوزانها سالب.

🎯 التالي: خوارزمية Floyd-Warshall — أقصر مسار بين كل أزواج العقد دفعة واحدة.