- المحطة الحالية
- محطة سابقة
- زوج مختصر
- المسار
خوارزمية فلويد-وارشال
كم تبعد كل مدينة عن كل مدينة أخرى؟ تجيب خوارزمية فلويد-وارشال عن ذلك دفعة واحدة، بجدول وثلاث حلقات متداخلة. تسمح كل جولة بعقدة أخرى محطةً في الطريق، وتسأل لكل زوج هل الالتفاف عبرها أقصر. تقدّم خطوة بخطوة لترى الجدول يمتلئ والمسافات تنخفض. اضغط «تشغيل» لمشاهدة الجدول وهو يمتلئ، أو «خطوة» و«رجوع» للتقدم خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع. يحمل الجدول أقصر مسافة وُجدت حتى الآن بين كل زوج من العقد؛ والرقم على كل حافة هو طولها. تسمح كل جولة بعقدة أخرى محطةً في الطريق، وتعرض كل خطوة زوجًا يصبح أقصر بالمرور بها. انقر على عقدة لتجعلها البداية؛ وحوّل النقر إلى «الهدف» ثم انقر على عقدة أخرى لترى أقصر مسار بينهما في النهاية. «رسم بياني جديد» ينشئ رسمًا آخر؛ اختر عدد عقده وحوافه. عند تحديد اللوحة، تتقدم مفاتيح الأسهم خطوة، ويشغّل مفتاح المسافة ويوقف مؤقتًا، وينتقل Home وEnd إلى البداية والنهاية.
كيف يعمل
- اضغط «تشغيل»، أو استخدم «خطوة» و«رجوع» للتحرك خطوة بخطوة. اسحب شريط الخطوات للانتقال إلى أي موضع.
- راقب الجدول: صف المحطة الحالية وعمودها ملوّنان، وكل خطوة تكتب مسافة أقصر.
- اختر البداية والهدف لترى أقصر مسار بينهما في النهاية. «رسم بياني جديد» ينشئ رسمًا آخر لتجربته.
كيف تعمل خوارزمية فلويد-وارشال
أنشئ جدولًا فيه صف وعمود لكل عقدة. املأ القطر بـ0، وطول الحافة حيث تتصل عقدتان، وما لا نهاية في كل مكان آخر. ثم خذ كل عقدة k بدورها محطةً محتملة. لكل زوج i وj، قارن مسافة الجدول من i إلى j بالمسافة من i إلى k مضافًا إليها المسافة من k إلى j، واحتفظ بالأصغر. بعد العقدة الأخيرة، تصبح كل خانة أقصر مسافة بين عقدتيها.
لماذا تنجح
بعد جولة k، يحمل الجدول لكل زوج أقصر مسار محطاته كلها من بين العقد التي عولجت حتى الآن. وجولة العقدة التالية لا تحتاج إلا إلى أن تقرر هل تساعد هذه العقدة: فأقصر مسار عبرها هو أقصر مسار إليها مع أقصر مسار منها، وكلاهما في الجدول بالفعل. وتُسمى طريقة بناء جواب كبير من أجوبة أصغر وُجدت من قبل البرمجة الديناميكية. وهي تعمل مع الحواف السالبة أيضًا، ويكشف عدد سالب على القطر عن دورة سالبة.
الأسئلة المتداولة
ما خوارزمية فلويد-وارشال؟
خوارزمية تجد أقصر مسافة بين كل زوج من العقد في رسم بياني موزون. تحتفظ بجدول للمسافات، وتفحص لكل عقدة بدورها هل يجعل المرور بها أي زوج أقصر.
ما سرعة خوارزمية فلويد-وارشال؟
فيها ثلاث حلقات متداخلة على العقد الـn، فيزداد العمل مع n³، ويحتاج الجدول إلى n² من الخانات. وهذا مناسب لرسوم فيها بضع مئات من العقد. أما في الرسوم الكبيرة المتفرقة فتشغيل خوارزمية ديكسترا من كل عقدة أسرع.
هل تتعامل خوارزمية فلويد-وارشال مع الحواف السالبة؟
نعم، ما دامت لا توجد دورة سالبة. فإن وُجدت، صارت خانة ما على القطر سالبة، وبهذا تكشفها خوارزمية فلويد-وارشال.
كيف أحصل على المسارات لا المسافات فقط؟
احتفظ بجدول ثانٍ فيه العقدة التالية في الطريق من i إلى j. وكلما صار زوج أقصر عبر k، انسخ العقدة التالية من i نحو k. واتّباع ذلك الجدول من i إلى j يرسم المسار.
هل يُرسل الرسم البياني إلى أي مكان؟
لا. يُنشأ الرسم البياني ويُملأ الجدول داخل متصفحك، وتبقى إعداداتك الأخيرة في التخزين المحلي لهذا المتصفح.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
الانتقال إلى المحرر