خوارزمية Ford-Bellman
لنحصل على رسم بياني مرجح موجه G برؤوس n وحواف m ، وبعض رؤوس البداية v . مطلوب إيجاد أطوال أقصر المسارات من الرأس v إلى جميع الرؤوس الأخرى.
مثل Dijkstra ، تبحث Ford-Bellman عن المسافة من قمة الرأس 1 إلى جميع العناصر الأخرى ، ولكن تعمل مع الحواف السالبة .
نبسب ؛
تتكون خوارزمية Ford-Bellman نفسها من عدة مراحل (
n-1 ). في كل مرحلة ، يتم فحص جميع حواف الرسم البياني ، وتحاول الخوارزمية الاسترخاء على طول كل حافة
(أ ، ب) من التكلفة ج . الاسترخاء على طول الحافة & [مدش]؛ هذه محاولة لتحسين معنى d [a] & nbsp؛ القيمة d [b] + c . في الواقع ، هذا يعني أننا نحاول تحسين إجابة الرأس باستخدام الحافة & nbsp؛ والجواب الحالي لأعلى.
المصفوفة d هي مصفوفة من أقصر الأطوال من قمة البداية ، تمامًا كما هو الحال في Dijkstra ، نملأها في البداية بأكبر عدد ممكن ، باستثناء قمة البداية ، التي تحتاج إلى وضعها 0.
لتخزين الحواف ، لا يتم استخدام مصفوفة متجاورة أو مصفوفة وزن ، ولكن قائمة تشير إلى أي عقدة تترك الحافة ( من ) ، والتي تأتي إليها ( إلى ) ووزنها ( cost ).
نبسب ؛
حافة الهيكل {
int من ، إلى ، تكلفة ؛
} ؛
ناقلات العلامة & lt ؛ حافة & GT ؛ حواف؛
يشير ثابت INF إلى الرقم "اللانهاية" - يجب اختياره بطريقة تتجاوز بوضوح جميع أطوال المسار الممكنة.
أبسط تطبيق للخوارزمية:
د [v] = 0 ؛
لـ (int i = 0 ؛ i & lt ؛ n-1 ؛ ++ i)
لـ (int j = 0 ؛ j & lt ؛ m ؛ ++ j)
نبسب ؛ نبسب ؛ نبسب ؛ إذا (د [حواف [ي]. من] & lt؛ INF)
نبسب ؛ نبسب ؛ على & nbsp ؛ على & nbsp ؛ على & nbsp ؛ د [حواف [ي]. إلى] = دقيقة (د [حواف [ي]. إلى] ، د [حواف [ي]. من] + حواف [ي]. تكلفة) ؛
أو أقصر قليلاً باستخدام بناء الجملة
C ++ 11 :
نبسب ؛
د [v] = 0 ؛
لـ (int i = 0 ؛ i & lt ؛ n-1 ؛ ++ i)
لـ (edge j: edges)
إذا (d [j.from] & lt؛ INF)
d [j.to] = min (d [j.to]، d [j.from] + j.cost) ؛
مثال العمل
خذ رسمًا بيانيًا بسيطًا موجهًا & nbsp؛ مع 5 عقد ، 4 حواف بوزن يساوي 1.
دعونا نقدم قائمة بالحواف بهذا الترتيب.
4 5 1
3 4 1
2 3 1
1 2 1
القيم الأولية في صفيف من أقصر الأطوال:
نبسب ؛
<الجسم>
| 0 |
inf |
inf |
inf |
inf |
حيث يجب أن يكون inf عددًا صحيحًا مطابقًا يكون دائمًا أكبر من وزن الحافة.
بعد التمريرة الأولى
نبسب ؛
بعد التمريرة الثانية
نبسب ؛
بعد التمريرة الثالثة
نبسب ؛
بعد الممر الرابع
نبسب ؛
إذا قمنا بتغذية الحواف بالترتيب من 1 إلى الأخير ، فيمكننا إيجاد أقصر أطوال بعد التمريرة الأولى.
نبسب ؛