تكرار السؤال: …
الإجابة المختصرة
تخفق ديكسترا عند وجود أضلاع ذات أوزان سالبة لأنها تفترض جشعاً (Greedy) أن المسار المحسوب لا يمكن أن يقصر مستقبلاً، بينما تعالج Bellman-Ford الأوزان السالبة وتكتشف الدورات السالبة (Negative Cycles).
الشرح
تستخدم ديكسترا طابور أولوية (Min-Priority Queue) وتصل لتعقيد O((V + E) log V). عند وجود ضلع سالب، قد تجد الخوارزمية مساراً يبدو أطول لكنه يصبح أقصر لاحقاً بفضل القيمة السالبة، مما يربك منطق التثبيت الجشع. خوارزمية Bellman-Ford تكرر عملية الاسترخاء (Relaxation) لجميع الأضلاع V-1 مرة بتعقيد O(V * E)، وإذا أمكن تقصير أي مسار في الخطوة V، فهذا دليل قاطع على وجود دورة سالبة تؤدي لانهيار مفهوم أقصر مسار (-Infinity).
مثال بالكود
import heapq
def dijkstra(graph, source): # correct only when all weights are >= 0
dist = {v: float("inf") for v in graph}
dist[source] = 0
heap = [(0, source)]
while heap:
d, u = heapq.heappop(heap)
if d > dist[u]:
continue # stale entry
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(heap, (dist[v], v))
return dist
def bellman_ford(graph, source): # O(V·E): supports negative weights
dist = {v: float("inf") for v in graph}
dist[source] = 0
for _ in range(len(graph) - 1):
for u in graph:
for v, w in graph[u]:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
for u in graph:
for v, w in graph[u]:
if dist[u] + w < dist[v]:
raise ValueError("negative cycle detected")
return distأخطاء شائعة
- تشغيل ديكسترا على شبكة مالية أو تحكيم عملات قد تحتوي على هوامش ربح سالبة، مما يعطي مسارات غير صحيحة.