الگوریتم فلوید وارشال (Floyd Warshall) – راهنمای کاربردی

در علوم کامپیوتر، «الگوریتم فلوید وارشال» (Floyd Warshall Algorithm) که با اسامی «الگوریتم فلوید» (Floyd's Algorithm)، «الگوریتم روی وارشال» (Roy–Warshall Algorithm)، «الگوریتم روی فلوید» (Roy–Floyd Algorithm) یا «الگوریتم دابلیواف‌آی» (WFI Algorithm) نیز شناخته شده است، از جمله الگوریتم‌های پیدا کردن کوتاه‌ترین مسیر در گراف وزن‌دار با وزن یال‌های مثبت یا منفی محسوب می‌شود (اما چرخه منفی وجود ندارد).

یک اجرای الگوریتم منجر به پیدا کردن طول‌های (مجموع وزن‌ها) کوتاه‌ترین مسیر بین همه جفت یال‌ها می‌شود. اگرچه، این مورد منجر به بازگرداندن جزئیاتی از خود مسیرها نمی‌شود، ولی این امکان وجود دارد که مسیرها با ویرایش‌های کوچکی در الگوریتم، بازسازی شوند. از نسخه‌های گوناگون این الگوریتم می‌توان برای پیدا کردن بستار تعدی رابطه R یا (در ارتباط با روش شولتسه) بزرگترین مسیر بین همه جفت یال‌ها در گراف وزن‌دار استفاده کرد.

در این مطلب، روش نوشتن الگوریتم فلوید وارشال بیان و پیاده‌سازی آن در زبان‌های برنامه‌نویسی گوناگون شامل «سی» (C)، «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java)، «پایتون» (Python)، «سی‌شارپ» (#C) و «پی‌اچ پی» (PHP) انجام شده است.

پیاده‌سازی الگوریتم فلوید وارشال

الگوریتم فلوید وارشال برای یافتن همه جفت کوتاه‌ترین مسیرها است. در واقع، مسئله پیدا کردن کوتاه‌ترین فاصله بین هر جفت از راس‌ها در گراف جهت‌دار وزن‌دار است. مثال زیر برای درک بهتر مطلب، قابل توجه است.

مثال: حل مسئله کوتاه‌ترین مسیر با الگوریتم فلوید وارشال

ورودی به صورت زیر است.

graph[][] = { {0,   5,  INF, 10},
                    {INF,  0,  3,  INF},
                    {INF, INF, 0,   1},
                    {INF, INF, INF, 0} }

ورودی بالا گرافی را نشان می‌دهد که در زیر قابل مشاهده است.

             10
       (0)------->(3)
        |         /|\
      5 |          |
        |          | 1
       \|/         |
       (1)------->(2)
            3

شایان توجه است که مقدار graph[i][j]‎ در صورتی که i برابر با j باشد، مساوی صفر است و اگر هیچ یالی از راس i به j وجود نداشته باشد، graph[i][j]‎ بی‌نهایت است. ماتریس کوتاه‌ترین مسیرها به صورت زیر است.

    0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

الگوریتم فلوید وارشال

ابتدا ماتریس پاسخ با مقادیر موجود در ماتریس گراف ورودی، مقداردهی اولیه می‌شود. سپس، ماتریس خروجی با در نظر گرفتن همه راس‌ها به عنوان یک راس میانی، به روز رسانی می‌شود. هدف، پیدا کردن یک به یک رأس‌ها و به روز رسانی همه کوتاه‌ترین مسیرهایی است که شامل راس‌های انتخاب شده به عنوان راس میانی در کوتاه‌ترین مسیر می‌شوند.

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

هنگامی که رأس شماره k به عنوان یک راس میانی انتخاب می‌شود، پیش‌تر، رأس‌های $$\left\{0, 1, 2, .. k-1\right\}$$ به عنوان راس‌های میانی انتخاب شده‌اند. برای هر جفت (i, j) از رأس‌های مبدأ و مقصد، دو حالت ممکن وجود دارد.

1. k یک رأس میانی در کوتاه‌ترین مسیر از i به j نیست. مقدار dist[i][j]‎ به صورتی که هست، حفظ می‌شود.
2. k یک رأس میانی در کوتاه‌ترین مسیر از i به j است. اگر dist[i][j] > dist[i][k] + dist[k][j]‎، مقادیر dist[i][j]‎ به صورت dist[i][k] + dist[k][j]‎ به روز رسانی می‌شود.

تصویری که در ادامه آمده است، نشان‌دهنده خصوصیات زیر ساختار بهینه بالا در مسئله کوتاه‌ترین مسیر برای همه جفت‌ها است.

در ادامه، پیاده‌سازی الگوریتم فلوید وارشال در زبان‌های برنامه‌نویسی گوناگون انجام شده است.

الگوریتم فلوید وارشال در ++C

الگوریتم فلوید وارشال در C

فیلم آموزش ساختمان داده ها – جامع و با نکات مهم + گواهینامه در فرادرس

کلیک کنید

الگوریتم فلوید وارشال در جاوا

الگوریتم فلوید وارشال در پایتون

فیلم آموزش نکات برنامه نویسی پایتون و حل مسائل الگوریتمی در فرادرس

کلیک کنید

الگوریتم فلوید وارشال در C#‎

الگوریتم فلوید وارشال در PHP

فیلم آموزش طراحی الگوریتم + حل مثال های عملی در فرادرس

کلیک کنید

خروجی قطعه کدهای بالا به صورت زیر است.

Following matrix shows the shortest distances between every pair of vertices
      0      5      8      9
    INF      0      3      4
    INF    INF      0      1
    INF    INF    INF      0

پیچیدگی زمانی روش بالا از درجه O(V³)‎ است. برنامه بالا، فقط کوتاه‌ترین مسیر را چاپ می‌کند. می‌توان این برنامه را به گونه‌ای ویرایش کرد که کوتاه‌ترین مسیرها را با ذخیره‌سازی اطلاعات اجداد آن‌ها در یک ماتریس دوبُعدی، نمایش دهد. همچنین، مقدار INF (بی‌نهایت) را می‌توان از limits.h به عنوان INT_MAX به دست آورد تا اطمینان حاصل شود که با بزرگ‌ترین مقدار ممکن کار شده است. هنگامی که INF به عنوان INT_MAX قرار داده می‌شود، نیاز به تغییر شرط if در برنامه بالا است تا از سرریز محاسباتی جلوگیری شود.

#include 

#define INF INT_MAX
..........................
if ( dist[i][k] != INF && 
     dist[k][j] != INF && 
     dist[i][k] + dist[k][j] < dist[i][j]
    )
 dist[i][j] = dist[i][k] + dist[k][j];
...........................

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

• مجموعه آموزش‌‌های برنامه‌‌ نویسی
• آموزش ساختمان داده‌ها
• مجموعه آموزش‌های ساختمان داده و طراحی الگوریتم
• رنگ‌آمیزی گراف به روش حریصانه — به زبان ساده
• الگوریتم دایجسترا (Dijkstra) — از صفر تا صد
• الگوریتم پریم — به زبان ساده
• متن کاوی (Text Mining) — به زبان ساده

^^