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

من ويكيبيديا، الموسوعة الحرة
اذهب إلى: تصفح، ‏ ابحث
Arwikify.svg يرجى إعادة صياغة هذه المقالة باستخدام التنسيق العام لويكيبيديا، مثل إضافة الوصلات والتقسيم إلى الفقرات وأقسام بعناوين.

خوارزمية بلمان - فورد تقوم بحساب الطريق الأقصر والأسرع في مخطط موجه من خلال مصدر القمة، على عكس خوارزمية دجكسترا فانها تقوم بحساب الحواف الموجهة السالبة (إضافة إلى الموجبة)، و تمت تسميتها نسبة للعالمين ريتشارد بلمان و فورد لستر. تسمح هذه الخوارزمية بوجود عدة أقواس أو دوائر ذات إتجاه سالب كما تسمح بالكشف عن وجود دوائر ماصة أي دوائر ذات وزن إجمالي سالب (إتجاه سالب)، قابلة للحصول من مصدر القمة.

الخوارزمية[عدل]

تعتمد هذه الخوارزمية على مقاربة البرمجة الديناميكية، تشبه في هيكلها الاساسي لخوارزمية دجكسترا ولكنها عوضاً عن إختيار العقدة الاقل وزناً والتي لم يتم تمديدها، فإنها تقوم بتمديد جميع الحواف وتقوم بذلك |ق-1| مرة، حيث |ق| هو عدد القمم في المخطط، التكرار يسمح بالحصول على أصغر مسافة ممكنة على طول المخطط، في حالة عدم وجود دوائر سالبة فإن الطريق الأقصر يمر على كل عقدة مرة واحدة على الأكثر.

الشفرة[عدل]

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

برهان صحتها[عدل]

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

Midori Extension.svg هذه بذرة مقالة تحتاج للنمو والتحسين. ساهم في إثرائها بالمشاركة في تحريرها.