‏Floyd-Warshall لجميع الأزواج

تحتاج أحيانًا إلى أقصر مسار بين كل زوج من العقد، لا من مصدر واحد فقط. تُعرف هذه بمشكلة جميع الأزواج.

تملأ خوارزمية Floyd-Warshall جدول مسافات كاملًا لجميع الأزواج باستخدام ثلاث حلقات متداخلة مرتبة، ومن دون إعداد يُذكر.

استخدم مصفوفة تكون فيها dist[i][j] أفضل تكلفة معروفة للانتقال من i إلى j. وابدأ بها من الحواف المباشرة المعطاة لك.

يمكن لكل عقدة الوصول إلى نفسها مجانًا، لذا عيّن قيمة القطر dist[i][i] إلى الصفر قبل بدء الإرخاء.

الحيلة هي السماح للمسارات بالمرور عبر عقدة وسيطة k، ثم التحقق مما إذا كان المرور عبر k أرخص من الانتقال المباشر.

تكون الحلقة الخارجية هي k، أي نقطة المنتصف المختارة. وتجرّب الحلقتان الداخليتان i وj كل زوج مقابل نقطة المنتصف تلك.

لكل زوج، أرخِ عبر k: فإذا كان الانتقال من i إلى k ثم إلى j أقصر، حدّث dist[i][j] إلى تلك التكلفة المجمعة.

عند انتهاء معالجة k، قد تستخدم جميع الأزواج عقدًا وسيطة تصل إلى k. ويضمن وضع k في الحلقة الخارجية صحة هذا الترتيب.

تقبل Floyd-Warshall الحواف السالبة، لكنها لا تقبل الدورات السالبة. وتترك الدورة السالبة قيمة قطرية ما أقل من الصفر.

تنتج ثلاث حلقات على n من العقد زمنًا قدره O(n^3) ومساحة قدرها O(n^2)، ولا يكون ذلك عمليًا إلا عندما يبقى n في حدود بضع مئات.

اختر Floyd-Warshall عندما يكون الرسم البياني صغيرًا وكثيفًا وتحتاج فعلًا إلى مسافة كل زوج، لا إلى مسافات مصدر واحد.

أي حلقة يجب أن تكون الخارجية في Floyd-Warshall؟

هيّئ مصفوفة، واجعل القطر يساوي صفرًا، ثم نفّذ الحلقات بالترتيب k, i, j وأرخِ عبر k. أقصر المسارات بين جميع الأزواج في O(n^3). 🧮