Bellman-Ford والحواف السالبة
معالجة القيم السالبة واكتشاف الدورات
Bellman-Ford والحواف السالبة درس مجاني في Competitive Programming Academy على CoddyKit. هذا هو الدرس 3 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Competitive Programming Academy، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
متى تفشل Dijkstra
تفترض Dijkstra أن المسافة التي أُخرجت نهائية، لكن قد تجعل حافة سالبة المسار أرخص لاحقًا. لذلك تفشل الخوارزمية.
إليك Bellman-Ford
تتعامل خوارزمية Bellman-Ford مع أوزان الحواف السالبة. وهي أبطأ من Dijkstra، لكنها موثوقة عندما لا يمكن الوثوق بالمنطق الجشع.
العملية الأساسية
تُرخي الخوارزمية كل حافة مرارًا: فإذا كانت dist[u] مضافًا إليها وزن الحافة أصغر من dist[v]، حدّث dist[v] إلى هذه القيمة الأصغر.
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wعدد الجولات
يستخدم أقصر مسار على الأكثر V - 1 حافة، لذلك تكفي V-1 جولة من إرخاء كل الحواف لتثبيت جميع المسافات.
for _ in range(n - 1):
relax_all_edges()هيّئ المسافات
ابدأ بجعل كل مسافة تساوي اللانهاية، باستثناء المصدر الذي تكون مسافته صفرًا، تمامًا كما تفعل في Dijkstra.
dist = [float('inf')] * n
dist[src] = 0مرور كامل واحد
يمر كل مرور على قائمة الحواف بأكملها مرة واحدة ويرخي كل حافة. وتنتشر التحسينات إلى الخارج بمقدار قفزة واحدة في كل مرور.
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + wلماذا تكفي V-1
بعد k من عمليات المرور، تكون جميع أقصر المسارات التي تستخدم k حواف صحيحة. وبعد V-1 عملية مرور، يكتمل كل أقصر مسار بسيط.
المرور الإضافي
نفّذ مرورًا إضافيًا واحدًا. فإذا انخفضت أي مسافة مجددًا، فهذا يعني أن هناك مسارًا يستمر في أن يصبح أرخص، ما يشير إلى دورة سالبة.
اكتشاف الدورات السالبة
تعني الدورة السالبة عدم وجود أقصر مسار محدود، إذ يمكنك الدوران بلا نهاية لخفض التكلفة دون حد.
for u, v, w in edges:
if dist[u] + w < dist[v]:
return 'negative cycle'زمن التنفيذ
ترخي E من الحواف عبر V من عمليات المرور، لذلك تعمل Bellman-Ford في O(V * E)، وهو مناسب للرسوم البيانية الصغيرة أو المتوسطة.
Dijkstra أم Bellman-Ford
اختر Dijkstra للأوزان غير السالبة وللسرعة. واختر Bellman-Ford عند ظهور أوزان سالبة أو عندما يتعين عليك اكتشاف دورة ضارة.
اختبار سريع
بعد V-1 عملية مرور، استمرت مسافة في الانخفاض أثناء مرور إضافي. ماذا يعني ذلك؟
مراجعة: Bellman-Ford
أرخِ جميع الحواف لمدة V-1 عملية مرور، ثم نفّذ مرورًا إضافيًا لاكتشاف الدورات السالبة. تعمل الخوارزمية في O(V*E)، لكنها تنجح حيث تفشل Dijkstra. ✅
الأسئلة الشائعة
هل درس «Bellman-Ford والحواف السالبة» مجاني؟
نعم — نص درس «Bellman-Ford والحواف السالبة» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Competitive Programming Academy، انتقل إلى CoddyKit PRO. تتضمن دورة Competitive Programming Academy 4 دروس في المجموع.
ماذا ستتعلم في «Bellman-Ford والحواف السالبة»؟
معالجة القيم السالبة واكتشاف الدورات تتمرن على Competitive Programming Academy مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Competitive Programming Academy؟
لا تُشترط خبرة سابقة. Competitive Programming Academy على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 3 من أصل 4.
كم من الوقت يستغرق درس «Bellman-Ford والحواف السالبة»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Competitive Programming Academy هذا؟
نعم. كل درس في Competitive Programming Academy يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- خوارزمية Dijkstra باستخدام كومة
- 0-1 BFS باستخدام Deque
- Bellman-Ford والحواف السالبة
- Floyd-Warshall لجميع الأزواج