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

خوارزمية بيلمان-فورد هي خوارزمية لحساب أقصر المسارات من رأس مصدر واحد إلى جميع الرؤوس الأخرى في رسم بياني موجه مُثقَّل . ^{[ 1 ]} وهي أبطأ من خوارزمية ديكسترا لنفس المشكلة، ولكنها أكثر تنوعًا، إذ يمكنها التعامل مع الرسوم البيانية التي تكون فيها بعض أوزان الحواف أعدادًا سالبة. ^{[ 2 ]} اقترح ألفونسو شيمبل هذه الخوارزمية لأول مرة ( 1955 ) ، ولكنها سُميت نسبةً إلى ريتشارد بيلمان وليستر فورد الابن ، اللذين نشراها في عامي 1958 و 1956 على التوالي. ^{[ 3 ]} كما نشر إدوارد ف. مور نسخة معدلة من الخوارزمية في عام 1959 ، ولهذا السبب تُسمى أحيانًا خوارزمية بيلمان-فورد-مور . ^{[ 1 ]} 

تُستخدم أوزان الحواف السالبة في تطبيقات متنوعة للرسوم البيانية، ولذا تُعد هذه الخوارزمية مفيدة. ^{[ 4 ]} إذا احتوى الرسم البياني على "دورة سالبة" (أي دورة مجموع حوافها قيمة سالبة) يمكن الوصول إليها من المصدر، فلن يكون هناك مسار أقل تكلفة : أي مسار يمر بنقطة على الدورة السالبة يمكن جعله أقل تكلفة بتجاوز الدورة السالبة مرة أخرى . في هذه الحالة، تستطيع خوارزمية بيلمان-فورد اكتشاف الدورة السالبة والإبلاغ عنها. ^{[ 1 ] [ 5 ]}

على غرار خوارزمية ديكسترا ، تعتمد خوارزمية بيلمان-فورد على أسلوب الاسترخاء ، حيث تُستبدل التقريبات للمسافة الصحيحة بتقريبات أفضل حتى الوصول إلى الحل. في كلتا الخوارزميتين، تكون المسافة التقريبية لكل رأس دائمًا أعلى من المسافة الحقيقية، ويتم استبدالها بأصغر قيمة بين قيمتها السابقة وطول المسار الجديد. ^{[ 6 ]}

مع ذلك، تستخدم خوارزمية ديكسترا قائمة انتظار ذات أولوية لاختيار أقرب رأس لم تتم معالجته بعد، وتُجري عملية الاسترخاء هذه على جميع حوافها الخارجة؛ في المقابل، تُرخي خوارزمية بيلمان-فورد جميع الحواف ببساطة، وتقوم بذلك.${\displaystyle |V|-1}$الأوقات، حيث${\displaystyle |V|}$يمثل عدد الرؤوس في الرسم البياني. ^{[ 6 ]}

في كل تكرار من هذه التكرارات، يزداد عدد الرؤوس ذات المسافات المحسوبة بشكل صحيح، مما يعني في النهاية أن جميع الرؤوس ستحصل على مسافاتها الصحيحة. تسمح هذه الطريقة بتطبيق خوارزمية بيلمان-فورد على نطاق أوسع من المدخلات مقارنةً بخوارزمية ديكسترا. تعتمد الإجابات الوسيطة والاختيارات بين المسارات القصيرة المتساوية على ترتيب الحواف التي تم تخفيفها، لكن المسافات النهائية تظل ثابتة. ^{[ 6 ]}

سباق بيلمان-فورد${\displaystyle O(|V|\cdot |E|)}$الوقت ، أين${\displaystyle |V|}$و${\displaystyle |E|}$يمثل عدد الرؤوس والحواف على التوالي.

دالة BellmanFord( قائمة الرؤوس، قائمة الحواف، مصدر الرؤوس ) هي// تأخذ هذه الدالة رسمًا بيانيًا، ممثلًا بقوائم من الرؤوس (ممثلة بأعداد صحيحة [0..n-1]) و // الحواف، وتملأ مصفوفتين (المسافة والسابق) // تحتويان على أقصر مسار من المصدر إلى كل رأس المسافة := قائمة بحجم n السابق := قائمة بحجم n// الخطوة 1: تهيئة الرسم البياني لكل رأس v في الرؤوس do // تهيئة المسافة إلى جميع الرؤوس إلى ما لا نهاية المسافة[v] := لا نهائي // وأن يكون له سلف فارغ previous[v] := null // المسافة من المصدر إلى نفسه تساوي صفرًا distance[source] := 0 // الخطوة 2: إرخاء الحواف بشكل متكرر، كرر |V|−1 مرة : لكل حافة (u, v) ذات وزن w في مجموعة الحواف ، إذا كان مجموع المسافة[u] + w < المسافة[v]، فقم بما يلي: المسافة[v] := المسافة[u] + w previous[v] := u // الخطوة 3: التحقق من وجود دورات ذات وزن سالب لكل حافة (u, v) ذات وزن w في قائمة الحواف do if distance[u] + w < distance[v] then previous[v] := u // توجد دورة سالبة؛ // البحث عن رأس في الدورة visited := قائمة بحجم n مهيأة بالقيمة false visited[v] := true while not visited[u] do visited[u] := true u := previous[u] // u رأس في دورة سالبة، // أوجد الدورة نفسها ncycle := [u] v := previous[u] بينما v لا يساوي u، نفّذ ncycle := concatenate([v], ncycle) v := previous[v] خطأ "يحتوي الرسم البياني على دورة ذات وزن سالب"، مسافة إرجاع الدورة، السلف

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

جوهر الخوارزمية هو حلقة تقوم بمسح جميع الحواف في كل دورة. لكل${\displaystyle i\leq |V|-1}$، في نهاية${\displaystyle i}$في التكرار رقم -، من أي رأس v ، باتباع مسار السلف المسجل في السلف ينتج عنه مسار له وزن إجمالي لا يتجاوز المسافة[v] ، وعلاوة على ذلك، فإن المسافة[v] هي حد أدنى لطول أي مسار من المصدر إلى v يستخدم على الأكثر i حواف.

بما أن أطول مسار ممكن بدون دورة يمكن أن يكون${\displaystyle |V|-1}$يجب مسح الحواف ضوئيًا${\displaystyle |V|-1}$يتم إجراء مسح نهائي لجميع الحواف، وإذا تم تحديث أي مسافة، فسيتم إنشاء مسار بطول${\displaystyle |V|}$تم العثور على حواف لا يمكن أن تحدث إلا إذا كانت هناك دورة سلبية واحدة على الأقل في الرسم البياني.

يجب أن يكون الضلع (u, v) الذي تم العثور عليه في الخطوة 3 قابلاً للوصول من دورة سالبة، ولكنه ليس بالضرورة جزءًا من الدورة نفسها، ولهذا السبب من الضروري تتبع مسار الأضلاع السابقة عكسيًا حتى يتم اكتشاف دورة. يستخدم الكود الزائف أعلاه مصفوفة منطقية ( visited) للعثور على رأس في الدورة، ولكن يمكن استخدام أي خوارزمية للعثور على الدورات للعثور على رأس في الدورة.

من التحسينات الشائعة عند تطبيق الخوارزمية، العودة مبكرًا عندما تفشل تكرارات الخطوة الثانية في تخفيف أي حواف، مما يعني أنه تم العثور على جميع أقصر المسارات، وبالتالي لا توجد دورات سالبة. في هذه الحالة، يتم تقليل تعقيد الخوارزمية من${\displaystyle O(|V|\cdot |E|)}$ل${\displaystyle O(l\cdot |E|)}$أين${\displaystyle l}$يمثل أقصى طول لأقصر مسار في الرسم البياني.

يمكن إثبات صحة الخوارزمية بالاستقراء : ^{[ 2 ] [ 7 ]}

اللمة . بعد i تكرارات لحلقة for ،

• إذا لم تكن المسافة ( u ) لانهائية، فإنها تساوي طول مسار ما من s إلى u ؛ و
• إذا كان هناك مسار من s إلى u يحتوي على i حافة على الأكثر ، فإن المسافة (u) هي على الأكثر طول أقصر مسار من s إلى u يحتوي على i حافة على الأكثر.

البرهان . في حالة الاستقراء الأساسية، لنفترض i=0أن لدينا النقطة قبل تنفيذ حلقة التكرار للمرة الأولى. عندئذٍ، بالنسبة للرأس المصدر، source.distance = 0يكون لدينا ، وهو صحيح. أما بالنسبة للرؤوس الأخرى u ، فيكون لدينا ، وهو صحيح أيضًا لأنه لا يوجد مسار من المصدر إلى u بدون حواف.u.distance = infinity

في حالة الاستقراء، نبرهن أولًا على الجزء الأول. لنفترض لحظةً يتم فيها تحديث مسافة رأس ما بمقدار . بافتراض الاستقراء، فإن هي طول مسار ما من المصدر إلى u . إذن ، هي طول المسار من المصدر إلى v الذي يتبع المسار من المصدر إلى u ثم ينتقل إلى v .v.distance := u.distance + uv.weightu.distanceu.distance + uv.weight

في الجزء الثاني، لنفترض أقصر مسار P (قد يكون هناك أكثر من مسار) من المصدر إلى v، بحيث لا يتجاوز عدد حوافه i . ولتكن u آخر رأس قبل v على هذا المسار. عندئذٍ، يكون جزء المسار من المصدر إلى u أقصر مسار من المصدر إلى u ، بحيث لا يتجاوز عدد حوافه i-1 ، لأنه لو لم يكن كذلك، لكان لا بد من وجود مسار أقصر منه تمامًا من المصدر إلى u، بحيث لا يتجاوز عدد حوافه i-1 ، وبالتالي يمكننا إضافة الحافة uv إلى هذا المسار لنحصل على مسار أقصر من P ، بحيث لا يتجاوز عدد حوافه i ، وهذا تناقض. بافتراض الاستقراء، بعد i -1 تكرار، يكون طول هذا المسار من المصدر إلى u على الأكثر هو . بالتالي، يكون طول P على الأكثر هو . في ^{التكرار} i ، تتم مقارنة مع ، ويتم مساواته بها إذا كان أصغر. لذلك، بعد i تكرار، يكون طول P على الأكثر هو ، أي طول أقصر مسار من المصدر إلى v الذي يستخدم i حواف على الأكثر .u.distanceuv.weight + u.distancev.distanceuv.weight + u.distanceuv.weight + u.distancev.distance

إذا لم تكن هناك دورات ذات وزن سالب، فإن كل مسار أقصر يمر بكل رأس مرة واحدة على الأكثر، لذا لا يمكن إجراء أي تحسينات إضافية في الخطوة 3. على العكس من ذلك، لنفترض أنه لا يمكن إجراء أي تحسين. عندئذٍ، لأي دورة ذات رؤوس v [0]، ...، v [ k -1]،

v[i].distance <= v[i-1 (mod k)].distance + v[i-1 (mod k)]v[i].weight

بجمع الحدود حول الدورة، يتم إلغاء الحدين v [ i ].distance و v [ i -1 (mod k )].distance، ليتبقى

0 <= sum from 1 to k of v[i-1 (mod k)]v[i].weight

أي أن لكل دورة وزن غير سالب.

عند استخدام الخوارزمية لإيجاد أقصر المسارات، يُشكل وجود الحلقات السالبة مشكلةً تمنع الخوارزمية من إيجاد إجابة صحيحة. مع ذلك، ولأنها تتوقف عند إيجاد حلقة سالبة، يُمكن استخدام خوارزمية بيلمان-فورد في التطبيقات التي يكون فيها هذا هو الهدف المنشود، كما هو الحال في تقنيات إلغاء الحلقات في تحليل تدفق الشبكة . ^{[ 1 ]}

يُستخدم شكلٌ مُوزّع من خوارزمية بيلمان-فورد في بروتوكولات توجيه متجه المسافة ، مثل بروتوكول معلومات التوجيه (RIP). ^{[ 8 ]} تُوصف الخوارزمية بأنها مُوزّعة لأنها تتضمن عددًا من العُقد (أجهزة التوجيه) ضمن نظام مستقل (AS) ، وهو عبارة عن مجموعة من شبكات بروتوكول الإنترنت (IP) التي عادةً ما تكون مملوكة لمزود خدمة الإنترنت (ISP). وتتألف من الخطوات التالية:

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

تتمثل العيوب الرئيسية لخوارزمية بيلمان-فورد في هذا السياق فيما يلي:

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

يمكن تحسين خوارزمية بيلمان-فورد عمليًا (وإن لم يكن ذلك في أسوأ الحالات) من خلال ملاحظة أنه إذا انتهت إحدى دورات الحلقة الرئيسية للخوارزمية دون إجراء أي تغييرات، فيمكن إنهاء الخوارزمية فورًا، حيث لن تُجري الدورات اللاحقة أي تغييرات أخرى. مع شرط الإنهاء المبكر هذا، قد تستخدم الحلقة الرئيسية في بعض الحالات عددًا أقل بكثير من | V |  -  1 من الدورات، على الرغم من أن أسوأ حالة للخوارزمية تظل دون تغيير. تحافظ التحسينات التالية جميعها على${\displaystyle O(|V|\cdot |E|)}$التعقيد الزمني في أسوأ الحالات.

يُقلل أحد أشكال خوارزمية بيلمان-فورد، التي وصفها مور (1959) ، من عدد خطوات الاسترخاء المطلوبة في كل تكرار للخوارزمية. فإذا لم تتغير قيمة المسافة للرأس v منذ آخر مرة تم فيها استرخاء حوافه ، فلا داعي لاسترخاء حوافه مرة أخرى. وبهذه الطريقة، مع ازدياد عدد الرؤوس ذات قيم المسافة الصحيحة، يتقلص عدد الرؤوس التي تحتاج حوافها الخارجة إلى الاسترخاء في كل تكرار، مما يؤدي إلى توفير ثابت في الوقت للرسوم البيانية الكثيفة . ويمكن تطبيق هذا الشكل من خلال الاحتفاظ بمجموعة من الرؤوس التي تحتاج حوافها الخارجة إلى الاسترخاء، وإزالة رأس من هذه المجموعة عند استرخاء حوافه، وإضافة أي رأس تغيرت قيمة مسافته في خطوة استرخاء إلى المجموعة. في الصين، شاع استخدام هذه الخوارزمية بفضل فاندينغ دوان، الذي أعاد اكتشافها عام 1994، تحت مسمى "خوارزمية أقصر مسار أسرع". ^{[ 9 ]}

وصف ين (1970) تحسينًا آخر لخوارزمية بيلمان-فورد. يتمثل تحسينه أولًا في تعيين ترتيب خطي عشوائي لجميع الرؤوس، ثم تقسيم مجموعة جميع الحواف إلى مجموعتين فرعيتين. تحتوي المجموعة الفرعية الأولى، E _{_f} ، على جميع الحواف ( vi , v _j ) حيث i < j ؛ بينما تحتوي المجموعة الفرعية الثانية، E _{_b} ، على الحواف ( vi , _{v j} ) حيث i > j . تتم زيارة كل رأس بالترتيب v_₁ , v_₂ , ..., v_{_{| V |}} ، مع تخفيف كل حافة صادرة من ذلك الرأس في E _{_f}. ثم تتم زيارة كل رأس بالترتيب v_{_{| V |}} , v _{_{| V |−1}} , ..., v_₁، مع تخفيف كل حافة صادرة من ذلك الرأس في E_{_b} . في كل تكرار للحلقة الرئيسية للخوارزمية، بعد التكرار الأول، تتم إضافة حافتين على الأقل إلى مجموعة الحواف التي تتطابق مسافاتها المُخففة مع مسافات أقصر مسار صحيحة: حافة من E _{_f} وحافة من E _{_b} . يقلل هذا التعديل عدد التكرارات في أسوأ الحالات للحلقة الرئيسية للخوارزمية من | V |  -  1 إلى${\displaystyle |V|/2}$[ ^{10 ] [ 11 ]​}

يُقدّم بانستر وإيبستين (2012) تحسينًا آخر، يستبدل الترتيب الخطي العشوائي للرؤوس المستخدم في تحسين ين الثاني بتبديل عشوائي . هذا التغيير يجعل أسوأ حالة لتحسين ين (حيث تتناوب حواف أقصر مسار بشكل صارم بين المجموعتين الفرعيتين E _f و E _b ) أمرًا مستبعدًا للغاية. مع ترتيب الرؤوس المُبدّل عشوائيًا، يكون العدد المتوقع للتكرارات المطلوبة في الحلقة الرئيسية على الأكثر${\displaystyle |V|/3}$[ ^{11 ]​}

قام فاينمان (2024) ، في جامعة جورج تاون ، بإنشاء خوارزمية محسّنة تعمل باحتمالية عالية في${\displaystyle {\tilde {O}}(|V|^{8/9}\cdot |E|)}$الوقت . هنا،${\displaystyle {\tilde {O}}}$هو شكل مختلف من تدوين Big O الذي يخفي العوامل اللوغاريتمية.