خوارزمية بلمان–فورد
في بعض مسائل أقصر المسارات حواف تجعل المسار أرخص: استرداد مبلغ، أو منحدر نازل، أو سعر صرف في صالحك. خوارزمية ديكسترا لا تقدر عليها. أما خوارزمية بلمان–فورد فتقدر، إذ تستبدل الصبر بالبراعة.
الفكرة
تعتمد كل خوارزميات أقصر المسارات على حركة واحدة هي إرخاء الحافة: إذا كان الذهاب إلى u ثم السير على الحافة u → v أقصر من أفضل طريق معروف إلى v، فاستخدمه. ترخي خوارزمية ديكسترا كل حافة مرة واحدة، بترتيب بارع لا ينجح إلا إذا لم تكن هناك حافة سالبة. أما بلمان–فورد فلا تفترض ذلك. بل ترخي كل حافة، بأي ترتيب ثابت، مرة بعد مرة، حتى تتوقف المسافات عن التغير.
خطوة بخطوة
أعطِ البداية المسافة 0 وكل عقدة أخرى ما لا نهاية. كرّر n − 1 مرة لـn من العقد: مرّ على كل حافة u → v وأرخِها إذا كانت لـu مسافة. توقف مبكرًا إذا لم تغيّر جولة كاملة شيئًا. ثم نفّذ جولة إضافية. إذا ظلت أي حافة قابلة للإرخاء، فثمة دورة مجموعها سالب يمكن الوصول إليها من البداية؛ وإلا فكل مسافة هي الأقصر، والعقد المحفوظة تعطي المسارات.
مثال
خذ الحواف أحادية الاتجاه A → B بطول 4، وA → C بطول 5، وB → D بطول 2، وC → B بطول −3، مفحوصة بهذا الترتيب، من A. تعطي الجولة 1 العقدة B القيمة 4 وC القيمة 5 وD القيمة 6، ثم تخفض C → B العقدة B إلى 5 − 3 = 2. تخفض الجولة 2 العقدة D إلى 2 + 2 = 4. لا تغيّر الجولة 3 شيئًا، فالجواب B 2 وC 5 وD 4. كانت خوارزمية ديكسترا ستجعل B نهائية عند 4 وD عند 6 قبل أن ترى الحافة السالبة. أضف حافة D → C بطول −4، فيصبح مجموع الدورة C → B → D → C هو −5: كل جولة تخفض المسافات من جديد، وتبلّغ جولة التحقق عن ذلك.
لماذا تكفي n − 1 جولة
أقصر مسار، إن وُجد، لا يكرر عقدة أبدًا، فلا تتجاوز حوافه n − 1. وإرخاء كل حافة في جولة يمدّ كل أقصر مسار معروف بشكل صحيح بحافة أخرى، أيًّا كان ترتيب الحواف. لذلك بعد الجولة k تكون كل أقصر المسارات ذات k حافة على الأكثر صحيحة، وبعد n − 1 جولة تكون كلها صحيحة. ومع ذلك يؤثر الترتيب في السرعة: قد ينتهي ترتيب جيد في جولة أو جولتين.
التاريخ والاستخدامات
وصف ألفونسو شيمبل (Alfonso Shimbel) الطريقة عام 1955، وليستر فورد الابن (Lester Ford Jr.) عام 1956، وإدوارد ف. مور (Edward F. Moore) عام 1957، وريتشارد بلمان (Richard Bellman) عام 1958؛ وهي تحمل اسمي اثنين منهم، بلمان وفورد. يمكن لكل موجّه أن ينفّذ جولاتها وحده، فصارت أساس بروتوكولات التوجيه بمتجه المسافة مثل RIP. وفي المال، يحوّل أخذ اللوغاريتم السالب لأسعار الصرف سلسلة مربحة من تبادلات العملات (المراجحة) إلى دورة سالبة، تستطيع بلمان–فورد إيجادها.
استكشفها
افتح التطبيق واضغط «خطوة». كل حافة أحادية الاتجاه، وبعض الأطوال سالبة. كل خطوة تفحص حافة واحدة بترتيب ثابت، وتعرض البطاقات الجولة وعدد المسافات التي غيّرتها. عادةً تأتي سريعًا جولة لا تغيّر شيئًا فيتوقف البحث مبكرًا. فعّل «أضف دورة سالبة» وشاهد المسافات تنخفض جولة بعد جولة حتى تجد جولة التحقق الدورة وترسمها باللون الأحمر.
الأسئلة المتداولة
ما التعقيد الزمني لبلمان–فورد؟
O(V · E)، حيث V عدد العقد وE عدد الحواف: V − 1 جولة على الأكثر، كل منها تفحص كل حافة. ومع الإيقاف المبكر تكون غالبًا أسرع بكثير في الواقع، وفي أفضل الحالات تكفي جولة واحدة.
ما الدورة السالبة؟
دورة مجموع أطوال حوافها أقل من صفر. الدوران حولها مرارًا يجعل المسار قصيرًا بقدر ما تشاء، فلا تكون أقصر المسافات معرّفة لأي عقدة يمكن الوصول إليها عبرها.
هل تعمل بلمان–فورد على الرسوم البيانية غير الموجهة؟
فقط إذا لم تكن هناك حافة سالبة: فالحافة السالبة غير الموجهة يمكن عبورها ذهابًا وإيابًا، وهذه بحد ذاتها دورة سالبة من حافتين. ومع حواف غير سالبة تعمل، لكن خوارزمية ديكسترا أسرع.
ما SPFA؟
خوارزمية Shortest Path Faster Algorithm، وهي صيغة من بلمان–فورد لا تعيد فحص إلا الحواف الخارجة من العقد التي تغيّرت مسافتها للتو، باستخدام طابور. وهي غالبًا أسرع بكثير، مع أن أسوأ حالاتها هي نفسها.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب بلمان–فورد