Bellman-Ford والدورات سالبة الوزن
نفّذ n-1 جولات من إرخاء جميع الحواف، واكتشف الدورات سالبة الوزن بجولة نهائية، واشرح سبب فشل Dijkstra مع الحواف سالبة الوزن.
Bellman-Ford والدورات سالبة الوزن درس مجاني في Coding Interview Prep على CoddyKit. هذا هو الدرس 2 من أصل 4. يمكنك قراءة الدرس كاملاً أدناه مجاناً — ثم تمرن عليه مباشرة في المتصفح باستخدام محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7. هذا الدرس جزء من مسار التعلم في Coding Interview Prep، وتقدمك يتزامن عبر الويب وتطبيق CoddyKit. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
لماذا توجد خوارزمية Bellman-Ford
تحل Bellman-Ford مسألة أقصر مسار من مصدر واحد مثل Dijkstra، لكنها تتعامل مع أوزان الحواف السالبة. كما أنها تكشف الدورات السالبة، وهي دورات يكون مجموع أوزانها سالبًا، مما يجعل من المستحيل تحديد أقصر مسار محدود يمر عبرها. وعلى الرغم من أنها أبطأ من Dijkstra، فإن Bellman-Ford هي الخيار الصحيح متى احتوى الرسم البياني على حواف ذات أوزان سالبة.
الإرخاء: العملية الأساسية
تعتمد Bellman-Ford على عملية واحدة هي الإرخاء. يعني إرخاء الحافة (u, v, w) ما يلي: إذا تحقق dist[u] + w < dist[v]، فحدّثوا dist[v] = dist[u] + w. نكرر إرخاء جميع الحواف. والفكرة الأساسية هي أن أي أقصر مسار يحتوي على V-1 حافة كحد أقصى في رسم بياني لا يحتوي على دورات سالبة. لذلك تكفي V-1 جولة من إرخاء جميع الحواف للعثور على جميع أقصر المسارات.
تنفيذ Bellman-Ford
مثّلوا الرسم البياني كقائمة حواف [(u, v, weight)]. هيّئوا dist[source] = 0 وجميع القيم الأخرى إلى inf. نفّذوا V-1 جولة، مع إرخاء جميع الحواف في كل جولة. يشير حدوث أي تحديث في الجولة V إلى وجود دورة سالبة.
def bellman_ford(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
# V-1 relaxation passes
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# V-th pass: detect negative cycle
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return None # negative cycle exists
return dist
edges = [(0,1,4),(0,2,5),(1,2,-3),(2,3,1)]
print(bellman_ford(4, edges, 0)) # [0, 4, 1, 2]لماذا تكفي V-1 جولة
يزور أقصر مسار في رسم بياني لا يحتوي على دورات سالبة كل عقدة مرة واحدة كحد أقصى، ولذلك يحتوي على V-1 حافة كحد أقصى. بعد الجولة 1، تصبح أقصر المسارات ذات الانتقال الواحد مثالية. وبعد الجولة 2، تصبح أقصر المسارات ذات الانتقالين مثالية. وبعد V-1 جولة، يكون قد عُثر على جميع أقصر المسارات، التي تستخدم V-1 انتقالًا كحد أقصى. إذا استمرت الجولة V في تحديث مسافة، فهذا يعني أن الرسم البياني يحتوي على دورة سالبة يمكن الوصول إليها من المصدر.
اكتشاف الدورات السالبة
بعد V-1 جولة، نفّذوا جولة إضافية واحدة على جميع الحواف. إذا حققت أي حافة (u, v, w) الشرط dist[u] + w < dist[v]، فتوجد دورة سالبة، وتكون أقصر مسافة إلى بعض العقد مساوية لـ -infinity. ومن تطبيقات ذلك في العالم الحقيقي اكتشاف فرص المراجحة في تبادل العملات (الدورات السالبة في الرسوم البيانية ذات الأوزان اللوغاريتمية)، واكتشاف التناقضات في أنظمة القيود.
def has_negative_cycle(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
# Nth pass
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
return True # negative cycle detected
return False
# Negative cycle: 1->2->3->1 with weights -1,-1,1 (sum=-1)
edges_neg = [(0,1,1),(1,2,-1),(2,3,-1),(3,1,1)]
print(has_negative_cycle(4, edges_neg, 0)) # Trueمقارنة بين Dijkstra وBellman-Ford
Dijkstra: زمنها O((V+E) log V)، وتتطلب أوزانًا غير سالبة، وتعتمد على الأسلوب الجشع. Bellman-Ford: زمنها O(V × E)، وتتعامل مع الأوزان السالبة، وتكشف الدورات السالبة. في معظم مسائل المقابلات ذات الأوزان غير السالبة، تُفضَّل Dijkstra. وعند ظهور أوزان سالبة، مثل مسائل «العثور على أقصر مسار مع حواف ذات تكلفة سالبة» أو «اكتشاف المراجحة»، تكون Bellman-Ford هي الحل. في الرسوم البيانية الكثيفة، تكون أسوأ حالة لـ Bellman-Ford، وهي O(V³)، مماثلة لـ Floyd-Warshall.
تطبيق: أرخص الرحلات الجوية باستخدام Bellman-Ford
يمكن حل مسألة Cheapest Flights Within K Stops (LeetCode 787) باستخدام نسخة معدّلة من Bellman-Ford: نفّذوا بالضبط k+1 من جولات الإرخاء، لأن k من التوقفات تعني k+1 حافة. استخدموا نسخة من المسافات من الجولة السابقة لضمان عدم استخدام انتقالات أكثر من المسموح في جولة واحدة، وإلا فقد تؤدي الجولة الواحدة إلى ربط عدة انتقالات متتالية.
def findCheapestPrice_bf(n, flights, src, dst, k):
dist = [float('inf')] * n
dist[src] = 0
for _ in range(k + 1): # k stops = k+1 edges
temp = dist[:] # copy to avoid using updated dist in same pass
for u, v, w in flights:
if dist[u] != float('inf') and dist[u] + w < temp[v]:
temp[v] = dist[u] + w
dist = temp
return dist[dst] if dist[dst] != float('inf') else -1
print(findCheapestPrice_bf(4,[[0,1,100],[1,2,100],[0,2,500]],0,2,1)) # 200SPFA: تحسين قائم على الطابور
إن Shortest Path Faster Algorithm (SPFA) هي نسخة محسّنة من Bellman-Ford، ولا تعيد إرخاء الحواف إلا انطلاقًا من العقد التي حُدّثت مسافاتها للتو، وذلك باستخدام طابور. يبلغ تعقيدها في الحالة المتوسطة O(E)، لكن أسوأ حالة تظل O(V × E). نادرًا ما تكون SPFA مطلوبة في المقابلات، لكن يمكنكم ذكرها كتحسين عندما تكون Bellman-Ford بطيئة جدًا على الرسوم البيانية قليلة الكثافة. لا توفر Python تطبيقًا مدمجًا لـ SPFA، لكن تنفيذها باستخدام collections.deque مباشر.
اكتشاف المراجحة في العملات
من التطبيقات الكلاسيكية لـ Bellman-Ford: إعطاء أسعار صرف العملات، ثم اكتشاف ما إذا كانت المراجحة ممكنة، أي وجود دورة تعيد عند تحويل العملات مبلغًا أكبر من المبلغ الذي بدأتم به. أجروا تحويلًا بأخذ اللوغاريتم السالب لأسعار الصرف. المراجحة = دورة ذات مجموع أوزان لوغاريتمية سالب = دورة سالبة يمكن لـ Bellman-Ford اكتشافها. يربط هذا التحويل مسائل مالية واقعية بالخوارزمية القياسية.
import math
def has_arbitrage(rates):
n = len(rates)
# Transform: -log(rate) converts product to sum
log_rates = [[-math.log(rates[i][j]) for j in range(n)] for i in range(n)]
edges = [(i,j,log_rates[i][j]) for i in range(n) for j in range(n) if i != j]
dist = [float('inf')] * n
dist[0] = 0
for _ in range(n - 1):
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u, v, w in edges:
if dist[u] + w < dist[v]:
return True # arbitrage!
return Falseتحسين الإنهاء المبكر
إذا لم تُحدَّث أي مسافة في جولة كاملة على جميع الحواف، فلن تُجري الجولات اللاحقة أي تحديث أيضًا، ولذلك يمكن الإنهاء مبكرًا. يقلل هذا التحسين التعقيد في أفضل الحالات إلى O(E)، عندما يكون الرسم البياني قد وصل إلى الحالة المثلى بعد عدد قليل من الجولات. أضيفوا العلامة updated = False في بداية كل جولة؛ فإذا بقيت False بعد انتهاء الجولة، فاخرجوا فورًا.
def bellman_ford_optimised(V, edges, source):
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
updated = False
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
updated = True
if not updated:
break # no more improvements possible
return distBellman-Ford على الرسوم البيانية ذات قوائم التجاور
عندما يُعطى الرسم البياني على شكل قائمة تجاور بدلًا من قائمة حواف، حوّلوه أولًا إلى قائمة حواف، أو كرّروا على جميع عناصر قوائم التجاور باعتبارها حواف. عند V=1000 وE=5000، تؤدي V-1=999 جولة، تمسح كل منها 5000 حافة، إلى 4,995,000 عملية، وهو عدد يقع ضمن حدود الزمن بسهولة. أما في الرسوم البيانية شديدة الكثافة (E ≈ V²)، فتتطابق أسوأ حالة O(V³) مع Floyd-Warshall، ولذلك يعتمد الاختيار على السياق.
from collections import defaultdict
def bellman_ford_adj(V, adj, source):
# Convert adjacency list to edge list
edges = [(u, v, w) for u in range(V) for v, w in adj[u]]
dist = [float('inf')] * V
dist[source] = 0
for _ in range(V - 1):
for u, v, w in edges:
if dist[u] != float('inf') and dist[u] + w < dist[v]:
dist[v] = dist[u] + w
return distتحقق سريع
اختبروا مدى فهمكم لمفاهيم Data Structures & Algorithms — Coding Interview Prep الواردة في هذا الدرس.
مراجعة الدرس
تعلّمتم في هذا الدرس أن Bellman-Ford ترخي جميع الحواف V-1 مرة للتعامل مع الحواف ذات الأوزان السالبة، وأن جولة الإرخاء رقم V التي تعثر على تحسينات إضافية تشير إلى وجود دورة سالبة، وأن زمن الخوارزمية هو O(V × E) مقارنةً بزمن Dijkstra البالغ O((V+E) log V). سنتناول بعد ذلك Floyd-Warshall لإيجاد أقصر المسارات بين جميع الأزواج ضمن عملية واحدة تعقيدها O(V³).
الأسئلة الشائعة
هل درس «Bellman-Ford والدورات سالبة الوزن» مجاني؟
نعم — نص درس «Bellman-Ford والدورات سالبة الوزن» كامل متاح مجاناً هنا على الويب. لتمرينه بشكل تفاعلي (محرر أكواد مدمج ومدرس ذكاء اصطناعي متاح 24/7) وفتح باقي دورة Coding Interview Prep، انتقل إلى CoddyKit PRO. تتضمن دورة Coding Interview Prep 4 دروس في المجموع.
ماذا ستتعلم في «Bellman-Ford والدورات سالبة الوزن»؟
نفّذ n-1 جولات من إرخاء جميع الحواف، واكتشف الدورات سالبة الوزن بجولة نهائية، واشرح سبب فشل Dijkstra مع الحواف سالبة الوزن. تتمرن على Coding Interview Prep مع أكواد عملية تشغلها مباشرة في المتصفح، ومدرس ذكاء اصطناعي متاح 24/7 يجيب على أسئلتك أثناء عملك.
هل أحتاج إلى خبرة سابقة لأبدأ Coding Interview Prep؟
لا تُشترط خبرة سابقة. Coding Interview Prep على CoddyKit منظم للمبتدئين حتى المتقدمين، لذا يمكنك البدء من هنا أو من البداية والتقدم بسرعتك الخاصة. هذا هو الدرس 2 من أصل 4.
كم من الوقت يستغرق درس «Bellman-Ford والدورات سالبة الوزن»؟
معظم دروس CoddyKit تستغرق حوالي 5–10 دقائق. كل منها موجز وتفاعلي، لذا تحرز تقدماً مستمراً وتستأنف من حيث توقفت عبر الويب والتطبيق.
هل يمكنني كتابة وتشغيل أكواد في درس Coding Interview Prep هذا؟
نعم. كل درس في Coding Interview Prep يتضمن محرر أكواد مدمج، لذا تكتب وتشغل أكواداً حقيقية مباشرة في متصفحك وتحصل على تعليقات فورية من الذكاء الاصطناعي — بدون إعداد محلي.
جميع الدروس في هذه الدورة
- خوارزمية Dijkstra مع طابور أولوية
- Bellman-Ford والدورات سالبة الوزن
- Floyd-Warshall: أقصر المسارات بين جميع الأزواج
- زمن تأخير الشبكة وإعادة بناء المسار