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

تحسبا لبدء الدورة التدريبية "الخوارزميات للمطورين" ، أعدوا ترجمة أخرى لمقال مثير للاهتمام.

---

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

لقد ناقشنا بالفعل خوارزمية ديكسترا كوسيلة لحل هذه المشكلة. خوارزمية ديكسترا هي خوارزمية جشعة ، وتعقيدها هو O (VLogV) (باستخدام كومة فيبوناتشي). ومع ذلك ، فإن Dijkstra لا يعمل مع الرسوم البيانية ذات الأوزان السلبية للحافة ، بينما Bellman-Ford بالكامل. تعد خوارزمية Bellman-Ford أبسط من خوارزمية Dijkstra ، وهي مناسبة تمامًا للأنظمة الموزعة. في الوقت نفسه ، فإن تعقيدها هو O (VE) ، وهو أكثر من مؤشر لوغاريتم ديكسترا.

التوصية : قبل الانتقال إلى عرض الحل ، حاول ممارسة نفسك.

خوارزمية

فيما يلي خطوات مفصلة.

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

1. في هذه الخطوة ، تتم تهيئة المسافات من القمة الأولية إلى جميع الرؤوس الأخرى على أنها غير محدودة ، ويفترض أن تكون المسافة إلى src نفسها هي 0. يوجد صفيف dist[] الحجم |V| مع كل القيم التي تساوي اللانهاية ، باستثناء عنصر dist[src] ، حيث يمثل src الرأس الأصلي.
2. الخطوة الثانية بحساب أقصر المسافات. يجب تنفيذ الخطوات التالية |V| -1 مرات ، حيث |V| - عدد القمم في هذا الرسم البياني.
   
   • قم بتنفيذ الإجراء التالي لكل حافة للأشعة فوق البنفسجية :
     إذا كان dist[v] > dist[u] + uv ، dist[v] بتحديث dist[v]
dist [v] = dist [u] + uv
     
3. في هذه الخطوة ، يتم الإبلاغ عما إذا كانت دورة الوزن السالب موجودة في الرسم البياني. لكل حافة uv ، قم بما يلي:
   
   
   • إذا كان dist[v] > dist[u] + uv ، فإن الرسم البياني يحتوي على دورة من الوزن السلبي.
     

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

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

مثال

لنلقِ نظرة على الخوارزمية في مثال الرسم البياني التالي. الصور التي التقطت من هنا .
دع القمة الأولية هي 0. خذ جميع المسافات كما لا حصر له ، باستثناء المسافة إلى src نفسه. إجمالي عدد القمم في الرسم البياني هو 5 ، لذلك تحتاج جميع الحواف إلى الذهاب 4 مرات.



اترك الضلوع بالترتيب التالي: (B ، E) ، (D ، B) ، (B ، D) ، (A ، B) ، (A ، C) ، (D ، C) ، (B ، C) ، ( E ، D). نحصل على المسافات التالية عندما تم الانتهاء من المرور على طول الضلوع لأول مرة. يعرض السطر الأول المسافات الأولية ، بينما يعرض السطر الثاني المسافات عند معالجة الحواف (B ، E) ، (D ، B) ، (B ، D) و (A ، B). يعرض السطر الثالث مسافة المعالجة (A ، C). يعرض السطر الرابع ما يحدث عند معالجة (D ، C) ، (B ، C) و (E ، D).



يضمن التكرار الأول أن جميع أقصر المسارات لم تعد أطول من مسار 1 حافة. نحصل على المسافات التالية عند اكتمال المرور الثاني على جميع الحواف (يعرض السطر الأخير القيم النهائية).



يضمن التكرار الثاني أن يبلغ طول كل المسارات الأقصر حدين على الأكثر. تعمل الخوارزمية على طول جميع الحواف 2 مرات أخرى. يتم تقليل المسافات بعد التكرار الثاني ، وبالتالي لا يقوم التكراران الثالث والرابع بتحديث قيم المسافة.

التنفيذ:

 # Python program for Bellman-Ford's single source # shortest path algorithm. from collections import defaultdict # Class to represent a graph class Graph: def __init__(self, vertices): self.V = vertices # No. of vertices self.graph = [] # default dictionary to store graph # function to add an edge to graph def addEdge(self, u, v, w): self.graph.append([u, v, w]) # utility function used to print the solution def printArr(self, dist): print("Vertex Distance from Source") for i in range(self.V): print("% d \t\t % d" % (i, dist[i])) # The main function that finds shortest distances from src to # all other vertices using Bellman-Ford algorithm. The function # also detects negative weight cycle def BellmanFord(self, src): # Step 1: Initialize distances from src to all other vertices # as INFINITE dist = [float("Inf")] * self.V dist[src] = 0 # Step 2: Relax all edges |V| - 1 times. A simple shortest # path from src to any other vertex can have at-most |V| - 1 # edges for i in range(self.V - 1): # Update dist value and parent index of the adjacent vertices of # the picked vertex. Consider only those vertices which are still in # queue for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: dist[v] = dist[u] + w # Step 3: check for negative-weight cycles. The above step # guarantees shortest distances if graph doesn't contain # negative weight cycle. If we get a shorter path, then there # is a cycle. for u, v, w in self.graph: if dist[u] != float("Inf") and dist[u] + w < dist[v]: print "Graph contains negative weight cycle" return # print all distance self.printArr(dist) g = Graph(5) g.addEdge(0, 1, -1) g.addEdge(0, 2, 4) g.addEdge(1, 2, 3) g.addEdge(1, 3, 2) g.addEdge(1, 4, 2) g.addEdge(3, 2, 5) g.addEdge(3, 1, 1) g.addEdge(4, 3, -3) # Print the solution g.BellmanFord(0) # This code is contributed by Neelam Yadav 

قيم الإخراج:



ملاحظات:

1. تم العثور على الأوزان السلبية في مختلف تطبيقات الرسم البياني. على سبيل المثال ، بدلاً من زيادة تكلفة المسار ، يمكننا الاستفادة باتباع مسار معين.
2. تعمل خوارزمية Bellman-Ford بشكل أفضل للأنظمة الموزعة (أفضل من خوارزمية ديكسترا). على عكس Dijkstra ، حيث نحتاج إلى إيجاد الحد الأدنى لقيمة كل القمم ، في Bellman Ford ، تعتبر الحواف واحدة في كل مرة.

التمارين:

1. تُبلغ خوارزمية Bellman-Ford القياسية عن أقصر الطرق فقط إذا لم يكن بها دورات ذات وزن سلبي. قم بتعديله بحيث يبلغ عن أقصر المسارات حتى لو كانت هناك مثل هذه الدورة.
2. هل يمكننا استخدام خوارزمية ديكسترا للعثور على أقصر الطرق في الرسم البياني مع الأوزان السلبية؟ هناك فكرة من هذا القبيل: حساب الحد الأدنى لقيمة الوزن ، وإضافة قيمة موجبة (تساوي القيمة المطلقة لقيمة الحد الأدنى للوزن) إلى جميع الأوزان وتشغيل خوارزمية Dijkstra للرسم البياني المعدل. هل تعمل مثل هذه الخوارزمية؟

تنفيذ بسيط لخوارزمية بيلمان فورد

مصادر:

www.youtube.com/watch؟v=Ttezuzs39nk
en.wikipedia.org/wiki/Bellman٪E2٪80٪93Ford_algorithm
www.cs.arizona.edu/classes/cs445/spring07/ShortestPath2.prn.pdf