خوارزمية Dijkstra ببايثون: دليل شامل لإيجاد أقصر مسار في الرسوم البيانية 🧭

مقدمة: ضعت في نابلس واكتشفت Dijkstra!

بتذكر مرة، كنت في نابلس، المدينة القديمة بشوارعها المتعرجة زي المتاهة. كان معي خريطة، بس بصراحة، ما فهمت منها شي! 😅 كنت بدي أوصل لمحل بيبيع كنافة نابلسية أصلية (مين ما بدو؟)، وضعت! قعدت أفكر: كيف ممكن الكمبيوتر يلاقي أقصر طريق بين نقطتين؟ وقتها تذكرت خوارزمية Dijkstra، الخوارزمية اللي بتساعدنا نلاقي أقصر مسار في الرسوم البيانية.

في هالمقالة، رح نشرح خوارزمية Dijkstra بالتفصيل، ورح نطبقها عملياً باستخدام بايثون. سواء كنت مبرمج مبتدئ أو محترف، هالمقالة رح تعطيك فهم قوي للخوارزمية وكيف تستخدمها لحل مشاكل حقيقية.

ما هي خوارزمية Dijkstra؟

خوارزمية Dijkstra (تلفظ “دايكسترا”) هي خوارزمية تستخدم لإيجاد أقصر مسار بين عقدة بداية (source node) وجميع العقد الأخرى في رسم بياني موجه (directed graph) أو غير موجه (undirected graph) ذي أوزان موجبة (non-negative weights). ببساطة، بتعطيك أقصر طريق من مكان لمكان، مع الأخذ في الاعتبار المسافات بين الأماكن.

مبدأ عمل الخوارزمية:

1. التهيئة: نبدأ بتحديد عقدة البداية. نعطيها مسافة صفر، وباقي العقد نعطيها مسافة لانهائية (∞).
2. الزيارة: نختار العقدة الأقرب (الأقل مسافة) اللي ما زرناها بعد.
3. التحديث: لكل جيران العقدة اللي اخترناها، نحسب المسافة من عقدة البداية عبر العقدة الحالية. إذا كانت المسافة الجديدة أقصر من المسافة الحالية للجيران، بنحدث المسافة.
4. التكرار: نكرر الخطوتين 2 و 3 حتى نزور كل العقد.

مثال عملي: رسم بياني بسيط

تخيل عندك رسم بياني بسيط فيه 5 عقد (A, B, C, D, E) والمسافات بينهم كالتالي:

• A -> B: 4
• A -> C: 2
• B -> C: 1
• B -> D: 5
• C -> D: 8
• C -> E: 10
• D -> E: 2

بدنا نلاقي أقصر مسار من العقدة A لكل العقد الأخرى.

تطبيق خوارزمية Dijkstra خطوة بخطوة:

1. التهيئة:
   • A: 0
   • B: ∞
   • C: ∞
   • D: ∞
   • E: ∞
2. الزيارة: نبدأ بالعقدة A (أقصر مسافة).
3. التحديث:
   • A -> B: 0 + 4 = 4 (أقصر من ∞، بنحدث B لتصبح 4)
   • A -> C: 0 + 2 = 2 (أقصر من ∞، بنحدث C لتصبح 2)
4. الزيارة: نختار العقدة C (أقصر مسافة غير مزورة).
5. التحديث:
   • C -> D: 2 + 8 = 10 (أقصر من ∞، بنحدث D لتصبح 10)
   • C -> E: 2 + 10 = 12 (أقصر من ∞، بنحدث E لتصبح 12)
6. الزيارة: نختار العقدة B (أقصر مسافة غير مزورة).
7. التحديث:
   • B -> C: 4 + 1 = 5 (أطول من 2، ما بنحدث)
   • B -> D: 4 + 5 = 9 (أقصر من 10، بنحدث D لتصبح 9)
8. الزيارة: نختار العقدة D.
9. التحديث:
   • D -> E: 9 + 2 = 11 (أقصر من 12، بنحدث E لتصبح 11)
10. الزيارة: نختار العقدة E.
11. لا يوجد تحديثات أخرى.

النتيجة النهائية:

• A: 0
• B: 4
• C: 2
• D: 9
• E: 11

هيك عرفنا أقصر مسافة من A لكل العقد الأخرى.

تطبيق خوارزمية Dijkstra ببايثون

هون رح نكتب كود بايثون بسيط لتطبيق خوارزمية Dijkstra.

import heapq

def dijkstra(graph, start):
    """
    حساب أقصر مسار من عقدة البداية إلى جميع العقد الأخرى في الرسم البياني.

    Args:
        graph (dict): تمثيل الرسم البياني كقاموس.
                       المفاتيح هي العقد، والقيم هي قواميس أخرى تمثل الجيران والمسافات.
        start (str): عقدة البداية.

    Returns:
        dict: قاموس يحتوي على أقصر المسافات من عقدة البداية إلى كل عقدة أخرى.
    """
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]  # قائمة الانتظار ذات الأولوية (المسافة، العقدة)

    while pq:
        dist, node = heapq.heappop(pq)

        if dist > distances[node]:
            continue

        for neighbor, weight in graph[node].items():
            distance = dist + weight

            if distance < distances[neighbor]:
                distances[neighbor] = distance
                heapq.heappush(pq, (distance, neighbor))

    return distances

# مثال على رسم بياني
graph = {
    'A': {'B': 4, 'C': 2},
    'B': {'C': 1, 'D': 5},
    'C': {'D': 8, 'E': 10},
    'D': {'E': 2},
    'E': {}
}

# حساب أقصر المسافات من العقدة 'A'
shortest_distances = dijkstra(graph, 'A')
print(shortest_distances) # Output: {'A': 0, 'B': 4, 'C': 2, 'D': 9, 'E': 11}

شرح الكود:

• `dijkstra(graph, start)`: الدالة الرئيسية اللي بتاخد الرسم البياني وعقدة البداية كمدخلات.
• `distances`: قاموس بخزن أقصر المسافات لكل عقدة. بنهيئها بقيمة لانهائية لكل العقد ما عدا عقدة البداية.
• `pq`: قائمة انتظار ذات أولوية (priority queue) بنستخدمها عشان نختار العقدة الأقرب أولاً.
• `heapq`: وحدة في بايثون بتوفر تنفيذ لقائمة الانتظار ذات الأولوية باستخدام الـ heap.
• الحلقة `while pq` بتستمر لحد ما نفضي كل العقد اللي لازم نزورها.
• داخل الحلقة، بنختار العقدة الأقرب، وبنحدث المسافات لجيرانها إذا لقينا طريق أقصر.

نصائح عملية من أبو عمر:

• استخدم `heapq` في بايثون: بتوفر أداء أفضل من القوائم العادية في إدارة قائمة الانتظار ذات الأولوية.
• تحقق من الأوزان السالبة: خوارزمية Dijkstra ما بتشتغل صح مع الأوزان السالبة. إذا كان عندك أوزان سالبة، استخدم خوارزمية Bellman-Ford.
• فكر في استخدامها في تطبيقات حقيقية: من خرائط جوجل لتوجيه حركة المرور، لخوارزميات الشبكات، خوارزمية Dijkstra موجودة في كل مكان!

الخلاصة: من كنافة نابلسية إلى خوارزميات! 🚀

خوارزمية Dijkstra هي أداة قوية جداً لحل مشاكل إيجاد أقصر مسار. من خلال فهمك للمبادئ الأساسية وتطبيقك العملي ببايثون، بتقدر تستخدمها في مجموعة واسعة من التطبيقات. تذكر، البرمجة زي الكنافة النابلسية، بدها شوية صبر وممارسة عشان تطلع بأفضل نتيجة! 😉

نصيحة أبو عمر: لا تخاف تجرب! العب بالكود، غير القيم، وشوف كيف الخوارزمية بتشتغل. هيك بتفهمها أحسن وبتصير جزء من مهاراتك.