خوارزمية Floyd-Warshall

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

Dijkstra وBellman-Ford يحسبان أقصر مسار من مصدر واحد لبقية العقد. لكن ماذا لو احتجت مصفوفة كاملة: أقصر مسافة بين كل زوج ممكن من العقد؟ تشغيل Dijkstra من كل عقدة على حدة يعطي هذا (بتعقيد إجمالي O(V × (V+E) log V))، لكن خوارزمية Floyd-Warshall تحسب نفس النتيجة مباشرة ببرمجة ديناميكية بسيطة — وتتعامل مع أوزان سالبة (بلا دورة سالبة) دون أي تعديل إضافي.

الفكرة: تجربة كل عقدة كنقطة وسيطة

الفكرة مركزية وبسيطة: لكل زوج عقد (i, j)، جرّب — هل المرور عبر عقدة وسيطة k يعطي مسارًا أرخص من الأفضل المعروف حاليًا؟

dist[i][j] = min( dist[i][j], dist[i][k] + dist[k][j] )

نكرّر هذا لكل k من 0 إلى V-1 (كل عقدة تُجرَّب كوسيط بدورها)، ولكل زوج (i, j) بكل مرة. الترتيب الخارجي على k أساسي: عند معالجة k، تكون dist[i][k] وdist[k][j] قد استقرّتا فعلًا (تشمل كل الوسطاء الأصغر من k)، ما يضمن صحّة النتيجة النهائية.

def floyd_warshall(num_nodes, edges):
    INF = float("inf")
    dist = [[INF] * num_nodes for _ in range(num_nodes)]
    for i in range(num_nodes):
        dist[i][i] = 0
    for u, v, weight in edges:
        dist[u][v] = weight  # افترض رسمًا موجّهًا

    for k in range(num_nodes):
        for i in range(num_nodes):
            for j in range(num_nodes):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]

    return dist


edges = [(0, 1, 3), (1, 2, 1), (0, 2, 10), (2, 3, 2)]
result = floyd_warshall(4, edges)
for row in result:
    print(row)
# [0, 3, 4, 6]   → أقصر مسار 0→2 أصبح 4 (عبر 1) بدل 10 مباشرة
# [inf, 0, 1, 3]
# [inf, inf, 0, 2]
# [inf, inf, inf, 0]

💡 الحلقات الثلاث المتداخلة (k، ثم i، ثم j) هي كل الخوارزمية — لا حاجة لأي هيكل بيانات مساعد (لا طابور أولويّة ولا مكدّس)، فقط مصفوفة ثنائية الأبعاد.

التعقيد

• الزمني: O(V³) — ثلاث حلقات متداخلة كل منها بحجم V.
• المكاني: O(V²) — مصفوفة المسافات الكاملة.

بسبب O(V³)، Floyd-Warshall مناسبة بشكل رئيسي للرسوم البيانية الصغيرة إلى المتوسطة الكثيفة حيث تحتاج فعلًا كل المسافات بين كل الأزواج. لرسم بياني كبير جدًا مع حاجة لمسار من مصدر واحد فقط، Dijkstra أو Bellman-Ford أنسب بكثير.

كشف الدورة السالبة

بعد تشغيل الخوارزمية، إن وجدت dist[i][i] < 0 لأي عقدة i (أي "المسافة من العقدة لنفسها" أصبحت سالبة)، فهذا يكشف وجود دورة سالبة تمرّ بتلك العقدة — تمامًا كما تفعل الجولة الإضافية في Bellman-Ford، لكن هنا الفحص بعد اكتمال الخوارزمية مباشرة بفحص القطر الرئيسي للمصفوفة.

مقارنة سريعة: أقصر المسارات الثلاثة

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

• جداول زمن الاستجابة بين خوادم الشبكة: حساب أقصر/أسرع مسار بين كل زوج خادمين دفعة واحدة بدل تشغيل الخوارزمية من كل خادم على حدة.
• الإغلاق الانتقالي (Transitive Closure) لرسم بياني: هل يوجد مسار أصلًا بين i وj؟ (نسخة مبسّطة تستبدل الجمع/المقارنة بعمليات منطقية).
• تحليل شبكات صغيرة الحجم (مواصلات، أنابيب) تحتاج مصفوفة مسافات كاملة.

أخطاء شائعة

• استخدامها على رسم بياني كبير جدًا (آلاف العقد) — O(V³) يصبح غير عملي بسرعة؛ استخدم Dijkstra من كل مصدر بدلًا منها هنا إن لم تكن هناك أوزان سالبة.
• نسيان ترتيب الحلقات (k يجب أن يكون الحلقة الخارجية) — أي ترتيب آخر يكسر منطق البرمجة الديناميكية ويعطي نتائج خاطئة.
• الظن أنها تتعامل مع دورة سالبة بشكل صحيح تلقائيًا — هي فقط تكشفها (عبر قطر المصفوفة)؛ النتائج لأي زوج يمرّ عبر تلك الدورة تبقى غير موثوقة.

🎯 التالي: الترتيب اللامقارَن (Counting Sort وRadix Sort) — كسر حاجز O(n log n) لأنواع بيانات معيّنة.