خوارزمية Dijkstra

المشكلة: أقصر مسار بوزن

تعلّمت BFS لإيجاد أقصر مسار (بعدد القفزات) برسم بياني غير موزون. لكن ماذا لو كانت الأضلاع لها أوزان مختلفة (مسافة، وقت، تكلفة)؟ BFS وحدها لا تكفي — هنا تأتي خوارزمية Dijkstra، أساس كل تطبيق ملاحة (Google Maps مثلًا يستخدم نسخًا محسّنة منها).

الفكرة الأساسية

ابدأ من نقطة المصدر، وتتبّع أرخص تكلفة معروفة حتى الآن لكل عقدة. بكل خطوة، اختر العقدة غير المُعالَجة الأرخص، وحدّث تكاليف جيرانها إن وجدت طريقًا أرخص عبرها ("الاسترخاء" — Relaxation).

مثال: أرخص طريق من A إلى كل مدينة أخرى

    A --6-- B
    |       |
    2       3
    |       |
    C --1-- D

المسافات النهائية من A: A=0, C=2, D=3, B=6 (عبر A→C→D→B = 2+1+3 = 6، أرخص من A→B=6 مباشرة بالتعادل)

التنفيذ بـ Python

import heapq

def dijkstra(graph, start):
    # graph: {node: [(neighbor, weight), ...]}
    distances = {node: float("inf") for node in graph}
    distances[start] = 0
    priority_queue = [(0, start)]  # (المسافة الحالية, العقدة)
    visited = set()

    while priority_queue:
        current_distance, current_node = heapq.heappop(priority_queue)

        if current_node in visited:
            continue
        visited.add(current_node)

        for neighbor, weight in graph[current_node]:
            distance = current_distance + weight
            if distance < distances[neighbor]:  # وجدنا طريقًا أرخص
                distances[neighbor] = distance
                heapq.heappush(priority_queue, (distance, 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}

لماذا نستخدم Priority Queue (كومة)؟

الخوارزمية تحتاج دائمًا أرخص عقدة غير معالَجة بأسرع وقت ممكن. Priority Queue (مبنية على Heap — راجع درس الأكوام) توفّر هذا بسرعة O(log n) بدل البحث الخطّي O(n) بكل خطوة، ما يحسّن التعقيد الكلي من O(n²) إلى O((V+E) log V).

شرط مهم: لا تعمل مع أوزان سالبة

Dijkstra تفترض أن إضافة ضلع لا يمكن أن "يُرخِّص" مسارًا مضى بالفعل — هذا يفشل مع أوزان سالبة (مسار طويل قد يصبح أرخص لاحقًا بضلع سالب). لأوزان سالبة، تحتاج خوارزمية Bellman-Ford بدلًا منها (أبطأ لكن تتعامل مع السالب).

التطبيقات الحقيقية

• تطبيقات الخرائط والملاحة (أقصر/أسرع طريق بين موقعين)
• بروتوكولات الشبكات (توجيه الحزم بأقل تكلفة)
• تحليل الشبكات الاجتماعية (أقرب مسار تواصل بين شخصين)

جدول سريع

أخطاء شائعة

• استخدام Dijkstra مع أوزان سالبة بالرسم البياني — نتائج خاطئة صامتة، لا تحذير واضح.
• نسيان تتبّع visited — يعيد معالجة نفس العقدة مرارًا ويبطّئ الخوارزمية بلا داعٍ (رغم أنها تبقى صحيحة).
• الخلط بينها وبين BFS — BFS لرسم غير موزون فقط، Dijkstra للأوزان الموجبة.

🎯 التالي: أقرب الجيران K — خوارزمية تصنيف بسيطة تُقدّم أساسيات التعلّم الآلي.