44. التعامل مع الأوزان السالبة: مقدمة إلى Bellman-Ford

تفشل خوارزمية Dijkstra's **** إذا كانت هناك أوزان سالبة للحواف لأن افتراضها الجشع (بأن الحد الأدنى للمسافة الذي تم العثور عليه حتى الآن نهائي) يمكن إبطاله بمسار لاحق يتضمن حافة سالبة.

خوارزمية Bellman-Ford

تحل Bellman-Ford مشكلة أقصر مسار لمصدر واحد حتى في الرسوم البيانية ذات الأوزان السالبة.

المفهوم الأساسي: الاسترخاء التكراري (Iterative Relaxation)

بدلاً من تثبيت المسارات بشكل جشع، تقوم Bellman-Ford بإرخاء (تحديث) جميع الحواف في الرسم البياني V-1 مرة بشكل متكرر (حيث V هو عدد الرؤوس).

1. تهيئة المسافات (المصدر=0، الباقي=ما لا نهاية).
2. التكرار V-1 مرة:
   • لكل حافة (U, V) في الرسم البياني:
     • إذا كان dist[U] + weight(U, V) < dist[V]، فقم بتحديث dist[V].

اكتشاف الدورات السالبة (Negative Cycles)

إذا قمنا بتشغيل خطوة الاسترخاء مرة V ووجدنا أنه لا يزال بإمكاننا إرخاء (تحديث) مسافة ما، فهذا يعني وجود دورة سالبة (negative cycle). تكون أقصر المسارات غير معرفة في الرسوم البيانية التي يمكن الوصول إليها من دورة سالبة.