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

برهان صحتها

يمكن إظهار صحة الخوارزمية بواسطة الاستقراء الرياضي: مبرهنة: بعد تكرار للدورات:

شرح مبسط

تعديل - تعديل مصدري - تعديل ويكي بيانات

شاركنا رأيك

التعليقات

لم يعلق احد حتى الآن .. كن اول من يعلق بالضغط هنا