خوارزمية بلمان فورد

في البداية، خوارزمية بلمان - فورد تقوم بحساب الطريق الأقصر والأسرع في مخطط موجه من خلال مصدر القمة، على عكس خوارزمية دجكسترا فانها تقوم بحساب الحواف الموجهة السالبة (إضافة إلى الموجبة)، و تمت تسميتها نسبة للعالمين ريتشارد بلمان وفورد لستر. ونتناول فيما يلي مزيدًا من التفاصيل.
وفي السياق ذاته، تسمح هذه الخوارزمية بوجود عدة أقواس أو دوائر ذات اتجاه سالب كما تسمح بالكشف عن وجود دوائر ماصة أي دوائر ذات وزن إجمالي سالب (اتجاه سالب)، قابلة للحصول من مصدر القمة.
المسافة [ق] = المسافة [ع] + و
- // الخطوة 3: التحقق من وجود دورات سلبية:
- لكل حافة (ق، ع) مع حواف ث الوزن في:
- إذا المسافة[ع] + و <المسافة[ق]:
- خطأ "الرسم البياني يحتوي على دورات سلبية"
الشفرة
وفي هذا السياق، // هذا التطبيق يأخذ في الرسم البياني، كما هو ممثل قوائم القمم والحواف، ويملى مسافة صفين.
- // الخطوة 1: بداية البيان:
- لكل قمة ق:
- إذا القمة هي المصدر فإن المسافة(ق) = 0
- وإلا فالمسافة(ق) = مالانهاية
- مع السلف = معدوم
في هذا الإطار، إجراءات بلمان - فورد(قائمة الحواف، قائمة القمم، مصدر القمة):
// الخطوة 2: تمديد الحواف مراراً
- لكل ر من 1 إلى حجم (القمم - 1):
- لكل حافة (ق، ع) مع الوزن (و) في الحواف :
- إذا المسافة[ع] + و <المسافة[ق]:
برهان صحتها
مبرهنة: بعد تكرار للدورات:
يمكن إظهار صحة الخوارزمية بواسطة الاستقراء الرياضي:
الخوارزمية
وفي هذا السياق، تعتمد هذه الخوارزمية على مقاربة البرمجة الديناميكية، تشبه في هيكلها الأساسي لخوارزمية دجكسترا ولكنها عوضاً عن اختيار العقدة الأقل وزناً والتي لم يتم تمديدها، فإنها تقوم بتمديد جميع الحواف وتقوم بذلك ق-1 – مرة، حيث ق – هو عدد القمم في المخطط، التكرار يسمح بالحصول على أصغر مسافة ممكنة على طول المخطط، في حالة عدم وجود دوائر سالبة فإن الطريق الأقصر يمر على كل عقدة مرة واحدة على الأكثر.
📝 هل في هذه المقالة خطأ؟
إذا وجدت معلومة تحتاج تصحيحاً أو إضافة، أو أردت حذف المقالة، أرسل لنا طلباً وسنراجعه.
ما رأيك في هذه المقالة؟