خوارزمية Ford-Bellman: هي نفسها Bellman-Ford وإليك كيف تعمل ومتى تستخدمها

إذا صادفت اسم Ford-Bellman في كتاب أو مسألة برمجية وتساءلت عمّا يعنيه، فالجواب المباشر: هو نفسه تماماً خوارزمية Bellman-Ford (بيلمان-فورد)، لا فرق بينهما إطلاقاً سوى ترتيب الاسمين. تجد أحياناً الترتيب معكوساً في المراجع الروسية والأوروبية القديمة، بينما اعتمدت المراجع الإنجليزية صيغة "Bellman-Ford"، وكلاهما يشير إلى الخوارزمية ذاتها التي تحسب أقصر مسار من عقدة مصدر واحدة إلى بقية العقد في رسم بياني موجّه، حتى لو احتوى على أوزان (تكاليف) سالبة.

فلا تضِع وقتك في البحث عن "خوارزمية Ford-Bellman" كأنها شيء منفصل؛ أي شرح أو كود لـ Bellman-Ford ينطبق عليها حرفياً.

لماذا اسمان لخوارزمية واحدة؟

سُمّيت على اسم ريتشارد بيلمان وليستر فورد الابن اللذين نشراها في خمسينيات القرن الماضي بشكل مستقل تقريباً. وأسهم فيها أيضاً إدوارد مور، لذا تراها أحياناً باسم Bellman–Ford–Moore. اختلاف الترتيب مجرد عُرف في التسمية لا أكثر، تماماً كما نقول "علي محمد" أو "محمد علي" لنفس الشخص.

ما المشكلة التي تحلّها؟

تخيّل خريطة مدن، وكل طريق بينها له "تكلفة": مسافة، أو زمن، أو رسوم. تريد أن تعرف أرخص طريقة للوصول من مدينتك إلى كل مدينة أخرى. هذه هي مشكلة أقصر مسار من مصدر واحد (Single-Source Shortest Path)، وبيلمان-فورد أداة كلاسيكية لحلّها.

ميزتها الأبرز أنها تتعامل مع الأوزان السالبة. الوزن السالب قد يمثّل حافزاً أو خصماً أو ربحاً على مسار ما (شائع في نمذجة المضاربة على العملات وتحليل الشبكات). خوارزمية Dijkstra الأشهر تنهار مع الأوزان السالبة، بينما بيلمان-فورد صُمّمت للتعامل معها.

كيف تعمل خطوة بخطوة

فكرتها الجوهرية عملية اسمها التخفيف (Relaxation): كلما وجدنا طريقاً أقصر إلى عقدة، نُحدّث المسافة المسجّلة إليها.

1. التهيئة: اجعل المسافة إلى المصدر = صفر، والمسافة إلى كل العقد الأخرى = ما لا نهاية (∞).
2. التكرار: كرّر على كل الحواف محاولة التخفيف: إذا كان مسافة(u) + وزن(u→v) < مسافة(v)، فحدّث مسافة(v). أعِد هذه الجولة الكاملة (عدد العقد − 1) مرة.
3. كشف الدورة السالبة: بعد انتهاء الجولات، مُرّ على الحواف جولة إضافية واحدة. إذا استطعت تخفيف أي حافة من جديد، فهذا يعني وجود دورة سالبة (حلقة مجموع أوزانها سالب) ولا يوجد "أقصر مسار" منطقي، لأن الدوران فيها يقلّل التكلفة إلى ما لا نهاية.

سبب تكرار الجولات (V − 1) مرة بالتحديد: أطول مسار بسيط بين عقدتين لا يمرّ بأكثر من V − 1 حافة، وكل جولة تضمن "استقرار" مسافة عقدة إضافية على الأقل.

كود مبسّط للتوضيح

def bellman_ford(vertices, edges, source):
    dist = {v: float('inf') for v in vertices}
    dist[source] = 0
    for _ in range(len(vertices) - 1):          # V - 1 جولة
        for u, v, w in edges:                    # كل حافة
            if dist[u] + w < dist[v]:
                dist[v] = dist[u] + w
    for u, v, w in edges:                        # جولة كشف الدورة السالبة
        if dist[u] + w < dist[v]:
            raise ValueError("يوجد دورة سالبة")
    return dist

بيلمان-فورد أم Dijkstra؟

هذا أكثر سؤال يتكرر. الاختيار يعتمد على طبيعة الرسم البياني:

المعيار	Bellman-Ford (Ford-Bellman)	Dijkstra
الأوزان السالبة	نعم، يتعامل معها	لا، تعطي نتائج خاطئة
كشف الدورات السالبة	نعم	لا
التعقيد الزمني	O(V × E) — أبطأ	O((V+E) log V) — أسرع
الفكرة	تخفيف كل الحواف مراراً	اختيار العقدة الأقرب جشعياً
الأنسب لـ	رسوم صغيرة/متوسطة فيها أوزان سالبة	رسوم كبيرة بأوزان موجبة فقط

الخلاصة العملية: إن كانت كل الأوزان موجبة وتريد السرعة، اختر Dijkstra. أما إن وُجدت أوزان سالبة أو أردت كشف الدورات السالبة، فبيلمان-فورد هو الخيار الصحيح.

تطبيقات واقعية

• بروتوكولات التوجيه في الشبكات: بروتوكول RIP القائم على "متجه المسافة" مبنيّ على الفكرة نفسها.
• المراجحة في أسواق العملات: تُحوَّل أسعار الصرف إلى أوزان (عبر اللوغاريتم)، ووجود دورة سالبة يعني فرصة ربح مراوغة.
• أنظمة النقل واللوجستيات: إيجاد أرخص أو أسرع مسار حين تتضمن بعض المقاطع حوافز أو تعويضات (قيم سالبة).

نصيحة عملية وخطأ شائع

الخطأ الأكثر تكراراً بين المبتدئين هو حذف جولة كشف الدورة السالبة والاكتفاء بجولات التخفيف. هذا يجعل الكود يُرجع أرقاماً تبدو صحيحة لكنها بلا معنى عند وجود دورة سالبة. نصيحتي: لا تعتبر تطبيقك لبيلمان-فورد مكتملاً قبل أن تضيف تلك الجولة الإضافية وتختبره على رسم بياني يحوي دورة سالبة عمداً. تحسين إضافي مفيد: أضف علماً (flag) يوقف الجولات مبكراً إذا مرّت جولة كاملة دون أي تحديث، فهذا يسرّع التنفيذ كثيراً على الرسوم المتفرقة.

الأسئلة الشائعة

هل Ford-Bellman و Bellman-Ford خوارزميتان مختلفتان؟ لا، إنهما اسمان لنفس الخوارزمية تماماً؛ الفرق في ترتيب الاسمين فقط حسب المرجع.

لماذا لا نستخدم Dijkstra دائماً ما دامت أسرع؟ لأن Dijkstra تفترض أن كل الأوزان موجبة. مع أي وزن سالب قد تعطي مسارات خاطئة، بينما بيلمان-فورد يبقى صحيحاً.

ما المقصود بالدورة السالبة ولماذا تُفسد الحساب؟ هي حلقة مغلقة مجموع أوزانها أقل من صفر. الدوران فيها يخفّض التكلفة بلا حد، فلا يعود لمفهوم "أقصر مسار" أي معنى، ولذلك تكتشفها الخوارزمية وتُبلّغ عنها.

ما تعقيدها الزمني؟ ‏O(V × E) حيث V عدد العقد وE عدد الحواف، أي أبطأ من Dijkstra لكنه مقبول تماماً للرسوم الصغيرة والمتوسطة.