خوارزمية فلويد-وارشال
كانت أطالس الطرق القديمة تضم جدولًا في آخرها: المسافة بين كل مدينتين. وخوارزمية فلويد-وارشال طريقة لحساب جدول كهذا، وهي من أقصر الخوارزميات التي كُتبت على الإطلاق: ثلاث حلقات ومقارنة واحدة، فتستقر كل أقصر المسافات في مكانها.
الفكرة
تجد خوارزمية ديكسترا وخوارزمية بلمان–فورد أقصر المسافات من بداية واحدة. أما خوارزمية فلويد-وارشال فتجدها من كل عقدة إلى كل عقدة أخرى دفعة واحدة، في جدول فيه صف وعمود لكل عقدة. تبدأ بما تقوله الحواف مباشرة، ثم تحسّن الجدول كله بالسماح بمزيد من العقد محطاتٍ في الطريق.
خطوة بخطوة
املأ الجدول: 0 من كل عقدة إلى نفسها، وطول الحافة بين الجيران، وما لا نهاية في غير ذلك. ثم لكل عقدة k، ولكل زوج i وj: إذا كانت المسافة من i إلى k مضافًا إليها المسافة من k إلى j أصغر من المسافة من i إلى j، فاكتب العدد الأصغر. هذه هي الخوارزمية كلها. وفي الشيفرة هي ثلاث حلقات، وk في الخارج.
مثال
خذ أربع عقد بالحواف A–B بطول 3، وB–C بطول 1، وA–C بطول 5، وC–D بطول 2. يبدأ الجدول بهذه الحواف، وما لا نهاية لـA–D وB–D. جولة A لا تغيّر شيئًا، لأن كل طريق عبر A أطول. وجولة B تجد من A إلى C عبر B: 3 + 1 = 4، وهو أقصر من 5. وجولة C تجد من A إلى D عبر C: 4 + 2 = 6، ومن B إلى D: 1 + 2 = 3، وكلاهما أول طريق يُعثر عليه. وجولة D لا تغيّر شيئًا. الجدول النهائي: A–B 3، وA–C 4، وA–D 6، وB–C 1، وB–D 3، وC–D 2.
لماذا يهم ترتيب الحلقات
يجب أن تكون المحطة k هي الحلقة الخارجية. بعد جولة k، تكون كل خانة أقصر مسافة باستخدام أول k من العقد فقط محطاتٍ، والجولة التالية تبني على ذلك: فأفضل مسار عبر المحطة الجديدة هو أفضل مسار إليها مع أفضل مسار منها، وكلاهما صحيح بالفعل. ووضع k في حلقة داخلية يكسر هذا الضمان وقد يترك مسافات خاطئة. أما تحديث الجدول في مكانه أثناء الجولة فآمن، لأن صف k نفسها وعمودها لا يتغيران في تلك الجولة.
التاريخ والاستخدامات
وصف Bernard Roy الطريقة عام 1959. وفي عام 1962 نشرها Stephen Warshall للإغلاق المتعدي، الذي يسأل فقط هل تستطيع عقدة الوصول إلى أخرى، ونشرها Robert Floyd لأقصر المسارات. وهي تحسب جداول المسافات وجداول التوجيه، وتجد قطر الشبكة، وتبيّن أي العقد تصل إلى أيها، وتكشف عن دورة سالبة بخانة سالبة على القطر.
استكشفها
افتح التطبيق واضغط «خطوة». الرسم البياني في جانب والجدول في الجانب الآخر. كل جولة تُبرز صف المحطة الحالية وعمودها؛ وكل خطوة تكتب المسافة الأقصر لزوج واحد وتحيط بإطار الخانتين اللتين جُمعتا. والخانات التي تغيّرت في هذه الجولة ملوّنة. اختر البداية والهدف لترى أقصر مسار بينهما عند اكتمال الجدول.
الأسئلة المتداولة
ما التعقيد الزمني لـخوارزمية فلويد-وارشال؟
O(n³) لـn من العقد، أيًّا كان عدد الحواف، وذاكرة O(n²) للجدول. وهي الطريقة المفضلة للرسوم الصغيرة أو الكثيفة، حيث تعمل حلقتها البسيطة بسرعة كبيرة.
فلويد-وارشال أم ديكسترا من كل عقدة؟
في الرسم الكثيف، أو حين يمكن أن تكون الحواف سالبة، تكون خوارزمية فلويد-وارشال أبسط وبالسرعة نفسها تقريبًا. أما في الرسم الكبير المتفرق ذي الحواف غير السالبة، فتشغيل خوارزمية ديكسترا من كل عقدة أسرع.
هل خوارزمية فلويد-وارشال برمجة ديناميكية؟
نعم. فهي تحل المسألة للمسارات التي محطاتها من بين أول k من العقد باستخدام الأجوبة لأول k − 1 من العقد، وتحتفظ بجدول واحد فقط تكتب فوقه وهي تتقدم.
ما الإغلاق المتعدي؟
جدول يبيّن أي العقد تصل إلى أيها، مع تجاهل المسافات. ونسخة Warshall من الخوارزمية تحسبه بـ"or" و"and" بدلًا من "min" و"+".
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب خوارزمية فلويد-وارشال