يجد كلاهما أقصر المسارات من مصدر في رسم بياني موزون. Dijkstra أسرع لكنه يتطلب أوزان غير سالبة؛ Bellman-Ford أبطأ لكنه يتعامل مع الحواف السالبة ويكتشف الدورات السالبة.
قم بتوسيع العقدة غير المزارة الأقرب بشكل متكرر وارخِ جيرانها.
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq) # closest first
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # relax edge
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
ارخِ جميع الحواف V-1 مرات؛ يعني الاسترخاء الإضافي وجود دورة سالبة.
| | Dijkstra | Bellman-Ford | |---|---------|| | الأوزان | غير سالبة | أي (بما فيها السالبة) | | الوقت | O((V+E) log V) | O(V·E) | | دورة سالبة | غير متاح | يكتشفها |
استخدم Dijkstra بشكل افتراضي للأوزان غير السالبة (الخرائط والشبكات). استخدم Bellman-Ford عند وجود حواف سالبة (مثل المراجحة). يتعطل Dijkstra بصمت على الأوزان السالبة — فخ كلاسيكي.
تقوم خوارزميات أقصر المسار بتشغيل التوجيه والملاحة والبروتوكولات الشبكية وتحليل تكاليف التبعيات.
معرفة قيد الوزن غير السالب على Dijkstra تمنع الإجابات الخاطئة في الواقع العملي.
فكرة الاسترخاء تربط بين التفكير الجشع وفكر البرمجة الديناميكية، مما يجعلها موضوعًا غنيًا على مستوى الخبراء.