خوارزمية Dijkstra Dijkstra's Algorithm

الصياغة

import heapq
distances = {node: float("inf") for node in graph}
distances[start] = 0
pq = [(0, start)]
while pq:
    dist, node = heapq.heappop(pq)
    for neighbor, weight in graph[node]:
        new_dist = dist + weight
        if new_dist < distances[neighbor]:
            distances[neighbor] = new_dist
            heapq.heappush(pq, (new_dist, neighbor))

📄 مثال

import heapq

def dijkstra(graph, start):
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    visited = set()
    while pq:
        dist, node = heapq.heappop(pq)
        if node in visited:
            continue
        visited.add(node)
        for neighbor, weight in graph[node]:
            new_dist = dist + weight
            if new_dist < distances[neighbor]:
                distances[neighbor] = new_dist
                heapq.heappush(pq, (new_dist, neighbor))
    return distances

graph = {"A": [("B", 6), ("C", 2)], "B": [("A", 6), ("D", 3)], "C": [("A", 2), ("D", 1)], "D": [("B", 3), ("C", 1)]}
print(dijkstra(graph, "A"))  # {'A': 0, 'B': 6, 'C': 2, 'D': 3}

أهم النقاط

💡 نصائح عملية

• تتبّع العقد التي عُولجت بالفعل (visited) لتفادي إعادة معالجتها من إدخالات قديمة بالكومة — لا يغيّر صحة النتيجة لكنه يحسّن الأداء

⚠️ أخطاء شائعة

• استخدامها مع أوزان سالبة بالرسم البياني — تُنتج نتائج خاطئة صامتة بلا أي خطأ أو تحذير واضح

خصائص ذات صلة