خوارزمية فلويد-وارشال (Floyd-Warshall): شرح مبسّط لإيجاد أقصر المسارات بين جميع النقاط

خوارزمية فلويد-وارشال (Floyd-Warshall) هي طريقة لإيجاد أقصر مسار بين كل زوج من النقاط في رسم بياني موزون، دفعة واحدة. أي أنك لا تحسب المسافة من نقطة واحدة إلى البقية فقط، بل تحصل على جدول كامل يخبرك بأقصر مسافة من أي نقطة إلى أي نقطة أخرى. تنتمي الخوارزمية إلى أسلوب البرمجة الديناميكية، وتتميز بأنها قصيرة جداً في الشيفرة (ثلاث حلقات متداخلة فقط) لكنها قوية بما يكفي للتعامل حتى مع الأوزان السالبة.

إن كنت طالب علوم حاسوب أو تستعد لمقابلة تقنية، فالفكرة الجوهرية التي يجب أن تخرج بها: فلويد-وارشال تحلّ مشكلة All-Pairs Shortest Paths، بينما خوارزميات مثل دايكسترا تحلّ Single-Source (من مصدر واحد فقط).

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

جوهر الخوارزمية سؤال بسيط يتكرر: هل المرور عبر نقطة وسيطة يجعل الطريق أقصر؟

تخيّل أنك تريد الذهاب من المدينة A إلى المدينة B. الطريق المباشر قد يكون طويلاً، لكن المرور عبر مدينة ثالثة C قد يختصر المسافة. فلويد-وارشال تفعل هذا بشكل منهجي: تأخذ كل نقطة وسيطة ممكنة، وتسأل عن كل زوج من النقاط: «هل المرور عبر هذه النقطة الوسيطة أرخص من الطريق الحالي؟». إن كان كذلك، تُحدّث المسافة.

القاعدة الحسابية التي تُطبَّق في كل خطوة هي:

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

أي: المسافة من i إلى j تساوي إمّا القيمة الحالية، أو مجموع الطريق من i إلى الوسيط k زائد الطريق من k إلى j — أيّهما أصغر.

كيف تعمل خطوة بخطوة

1. التهيئة: أنشئ مصفوفة مسافات dist بحجم V×V (حيث V عدد النقاط). ضع المسافة من كل نقطة إلى نفسها = صفر، والمسافة بين النقطتين المتصلتين بحافة = وزن الحافة، وبين النقطتين غير المتصلتين = ما لا نهاية (∞).
2. الحلقة الخارجية (k): مرّ على كل نقطة واعتبرها «الوسيط» المسموح استخدامه.
3. الحلقتان الداخليتان (i و j): لكل زوج من النقاط، طبّق قاعدة التحديث أعلاه.
4. النتيجة: بعد انتهاء الحلقات الثلاث، تحتوي المصفوفة على أقصر مسافة بين كل زوج من النقاط.

مثال مبسّط بلغة شبه برمجية:

for k in 0..V-1:
    for i in 0..V-1:
        for j in 0..V-1:
            if dist[i][k] + dist[k][j] < dist[i][j]:
                dist[i][j] = dist[i][k] + dist[k][j]

التعقيد الزمني والمكاني

• الزمن: O(V³) بسبب الحلقات الثلاث المتداخلة، حيث V عدد النقاط. لاحظ أن التعقيد يعتمد على عدد النقاط لا عدد الحواف.
• الذاكرة: O(V²) لتخزين المصفوفة.

هذا يعني أن الخوارزمية ممتازة للرسوم البيانية الصغيرة والمتوسطة والكثيفة (عدد حواف كبير)، لكنها تصبح بطيئة جداً عندما يكون عدد النقاط بالآلاف.

فلويد-وارشال أم دايكسترا أم بلمان-فورد؟

الخطأ الشائع هو اعتبار هذه الخوارزميات بدائل مباشرة لبعضها. كلٌّ منها يحلّ مشكلة مختلفة قليلاً:

المعيار	فلويد-وارشال	دايكسترا	بلمان-فورد
نوع المشكلة	كل الأزواج	مصدر واحد	مصدر واحد
الأوزان السالبة	مدعومة	غير مدعومة	مدعومة
كشف الدورات السالبة	نعم	لا	نعم
التعقيد الزمني	O(V³)	O(E log V)	O(V·E)
الأنسب لـ	رسوم صغيرة/كثيفة	رسوم كبيرة بأوزان موجبة	كشف الدورات السالبة من مصدر واحد

الخلاصة العملية: إن احتجت المسافات بين كل النقاط ولديك رسم بياني ليس ضخماً، فلويد-وارشال هي الأبسط والأنظف. أمّا إن كنت تريد المسار من نقطة واحدة فقط في رسم ضخم بأوزان موجبة، فدايكسترا أسرع بكثير.

نقطة قوة مهمة: الأوزان السالبة وكشف الدورات

على عكس دايكسترا، تتعامل فلويد-وارشال بشكل صحيح مع الحواف ذات الوزن السالب، وهي حالة تظهر في مسائل مثل أسعار الصرف أو تكاليف قد تتحول إلى ربح.

كما يمكنها كشف الدورة السالبة (negative cycle) بحيلة بسيطة: بعد انتهاء الحوسبة، افحص القطر الرئيسي للمصفوفة. إن وجدت أي قيمة dist[i][i] أصبحت أقل من الصفر، فهذا يعني وجود دورة سالبة تمرّ بالنقطة i — لأن المسافة من نقطة إلى نفسها يُفترض ألّا تقل عن صفر أبداً.

الخطأ الأكثر شيوعاً في التنفيذ

التفصيل الذي يُسقِط كثيراً من المبرمجين: ترتيب الحلقات. يجب أن تكون حلقة النقطة الوسيطة (k) هي الحلقة الخارجية، لا الداخلية. لو وضعت k في الداخل، ستحسب الخوارزمية نتائج خاطئة لأنها لن تكون قد جهّزت المسارات عبر الوسطاء السابقين قبل استخدامها. تذكّر دائماً: k أولاً، ثم i، ثم j.

خطأ آخر: استخدام قيمة كبيرة جداً لتمثيل «ما لا نهاية» ثم جمعها فتحدث فيضان عددي (overflow). الحل استخدام قيمة كبيرة معقولة والتحقق قبل الجمع.

أين تُستخدم عملياً؟

• الشبكات وبروتوكولات التوجيه: حساب أقصر المسارات بين عُقد الشبكة.
• أنظمة الخرائط والنقل: بناء جداول المسافات المسبقة بين محطات أو مدن محدودة العدد.
• تحليل الرسوم البيانية: حساب مقاييس مثل «المركزية» (centrality) التي تتطلب معرفة المسافات بين كل النقاط.
• الإغلاق المتعدّي (Transitive Closure): معرفة ما إذا كان يمكن الوصول من أي نقطة إلى أخرى.

الأسئلة الشائعة

هل تعمل فلويد-وارشال على الرسوم غير الموجّهة؟ نعم. الرسم غير الموجّه يُعامَل كرسم موجّه بحافتين متقابلتين لكل رابط. فقط تأكد من أن الأوزان السالبة في رسم غير موجّه تُنشئ فوراً دورة سالبة، فانتبه لذلك.

لماذا لا أستخدم دايكسترا لكل نقطة بدلاً منها؟ يمكنك ذلك، وقد يكون أسرع للرسوم المتفرّقة (قليلة الحواف). لكن دايكسترا لا تدعم الأوزان السالبة، وتكرارها لكل نقطة أعقد في التنفيذ من ثلاث حلقات بسيطة.

هل تعطيني الخوارزمية المسار نفسه أم المسافة فقط؟ افتراضياً تعطي المسافات فقط. لاسترجاع المسار الفعلي، احتفظ بمصفوفة إضافية next تسجّل النقطة التالية في كل مسار، ثم أعِد بناء المسار منها.

متى تكون غير مناسبة؟ عندما يكون عدد النقاط كبيراً جداً (آلاف)، لأن O(V³) يصبح مكلفاً. حينها فكّر في دايكسترا من المصادر التي تهمّك فقط.