Motivation
الدرس 2 من 9 في دورة خوارزمية Bellman-Ford - خوارزميات المخططات على Coddy.
يعتمد خوارزمية بيلمان-فورد على عملية واحدة، وهي الاسترخاء (relaxation): لحافة u -> v بوزن w، إذا كان المرور عبر u أرخص (dist[u] + w < dist[v])، فقم بتحديث dist[v]. كرر ذلك لكل حافة بشكل متكرر.
لماذا نتعلم خوارزمية بيلمان-فورد؟
- الأوزان السالبة: تعمل حيث لا تستطيع خوارزمية ديكسترا، على سبيل المثال التكاليف التي يمكن أن تكون خصومات أو مراجحة العملات.
- اكتشاف الدورات السالبة: تمريرة استرخاء إضافية واحدة تكشف عن الدورات التي يكون مجموع أوزانها سالباً.
- البساطة: لا تتطلب طابور أولويات، بل مجرد استرخاء متكرر للحواف.
المقايضة هي السرعة: O(V * E)، وهي أبطأ من خوارزمية ديكسترا O((V + E) log V).
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
