- الحالية
- لها مسافة
- حافة مستخدمة
- المسار
- دورة سالبة
خوارزمية بلمان–فورد
تتعطل خوارزمية ديكسترا عندما يكون طول حافة سالبًا، كطريق يدفع لك بدل أن يأخذ منك رسم عبور. أما خوارزمية بلمان–فورد فلا تتعطل: فهي ببساطة تفحص كل حافة مرارًا حتى لا يتحسن شيء، بل تستطيع أن تعرف متى تجعل دورةٌ المسافاتِ تنخفض بلا نهاية. انقر على عقدة لتبدأ منها وتقدّم عبر الجولات خطوة بخطوة. اضغط «تشغيل» لمشاهدة البحث، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. كل حافة أحادية الاتجاه كما يبيّن سهمها، والرقم عليها هو طولها، وقد يكون سالبًا. انقر على عقدة لتجعلها البداية؛ وحوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى لترى أقصر مسار إليها في النهاية. الرقم على كل عقدة هو مسافتها حتى الآن. فعّل «أضف دورة سالبة» لترى كيف تجد بلمان–فورد دورة كهذه. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.
كيف يعمل
- انقر على عقدة لتجعلها البداية. لرؤية مسار في النهاية، حوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى.
- اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع.
- فعّل «أضف دورة سالبة» لترى بلمان–فورد تجدها. «رسم بياني جديد» ينشئ رسمًا آخر لتجربته.
كيف تعمل بلمان–فورد
أعطِ البداية المسافة 0 وكل عقدة أخرى ما لا نهاية. ثم نفّذ جولات: في كل جولة افحص كل حافة u → v مرة واحدة. إذا كانت لـu مسافة وكان dist(u) مضافًا إليه طول الحافة أقصر من dist(v)، فاخفض dist(v) وتذكّر u طريقًا إليها. بعد الجولة k يصبح كل أقصر مسار يستخدم k من الحواف على الأكثر معروفًا. أقصر مسار يزور كل عقدة مرة واحدة على الأكثر، فلا تتجاوز حوافه n − 1، وتكفي n − 1 جولة دائمًا. وإذا لم تغيّر جولة كاملة شيئًا، يمكن إيقاف البحث مبكرًا.
إيجاد دورة سالبة
إذا كان مجموع حواف دورة أقل من صفر، فالدوران حولها مرة أخرى يجعل المسار أقصر دائمًا، فلا يوجد أقصر مسار أصلًا. وتلاحظ بلمان–فورد ذلك: بعد n − 1 جولة، يجب ألا تغيّر جولة إضافية شيئًا. فإذا ظلت حافة قابلة للإرخاء، فثمة دورة سالبة يمكن الوصول إليها من البداية، وتتبّع العقد المحفوظة رجوعًا من تلك الحافة يقود إليها. في التطبيق تُرسم الدورة باللون الأحمر.
الأسئلة المتداولة
ما خوارزمية بلمان–فورد؟
خوارزمية تجد أقصر المسارات من بداية واحدة إلى كل عقدة أخرى في رسم بياني قد تكون أطوال حوافه سالبة. ترخي كل حافة في جولات متكررة، وتبلّغ عن دورة سالبة إذا أمكن الوصول إلى واحدة من البداية.
لماذا تفشل خوارزمية ديكسترا مع الحواف السالبة؟
تجعل ديكسترا مسافة العقدة نهائية بمجرد أن تصبح الأقرب في الطابور. لكن حافة سالبة تُكتشف لاحقًا قد تعود إلى تلك العقدة بطريق أقصر، فتكون المسافة النهائية خاطئة. أما بلمان–فورد فلا تجعل أي مسافة نهائية مبكرًا؛ بل تواصل فحص كل حافة.
لماذا n − 1 جولة؟
لا يحتاج أقصر مسار أبدًا إلى زيارة عقدة مرتين، فلا تتجاوز حوافه n − 1. وكل جولة تمدّ أقصر المسارات المعروفة بحافة واحدة على الأقل، فبعد n − 1 جولة تكون كلها قد وُجدت.
ما سرعة بلمان–فورد؟
كل جولة تفحص كل الحواف وعددها E، وعدد الجولات V − 1 على الأكثر، فيزداد العمل بنسبة V × E. وهذا أبطأ من خوارزمية ديكسترا، ولهذا تُستخدم بلمان–فورد حين يمكن أن تكون الحواف سالبة.
هل يُرسل الرسم البياني إلى أي مكان؟
لا. يُنشأ الرسم البياني ويُبحث فيه داخل متصفحك، وتبقى إعداداتك الأخيرة في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر