مقدمه
یکی از الگوریتم های ساده که معمولا در درس ساختمان گسسته، طراحی الگوریتم و ساختمان داده به صورت پایه مطرح می شود الگوریتم فلوید وارشال می باشد. این الگوریتم با مرتبه O(N3) شاید یکی از بدترین انتخاب ها برای حل مسئله به علت کندی بیش از حد باشد. اما وقتی تعداد نود به اندازه کوچکتر از 200 باشد تفاوت قابل توجه ای با الگوریتم های خوب جایگزین ندارد و به علت پیاده سازی ساده و سریع این الگوریتم همیشه اگر در محدودیت های مساله قابل استفاده باشد جایگزین بقیه کاندید ها می شود.
رابرت فلوید و استفان وارشال همزمان باهم در مقالات مختلف در سال 1962 این الگوریتم را منتشر کردند، و به افتخارشان الگوریتم فلوید-وارشال نام گرفت که به اختصار به آن فلوید نیز گفته می شود، رابرت فلوید دارای یک الگوریتم خوب دیگر برای پیدا کردن دور در لیست پیوندی یا روابط بازگشتی بر اساس مقدار قبلی می باشد که باز با اسم الگوریتم فلوید مشهور است اما به اندازه این الگوریتم اعمال تعدی معروف نیست.
دلیل من برای انتخاب این الگوریتم برای بخش درسنامه الگوریتم ها، روزمره و ساده بودن الگوریتم فلوید بود که با توجه به بازدید های وبلاگ بنظر می رسد دانشجو های زیادی در طول ترم نیاز به مطالعه و استفاده از این الگوریتم دارند.

ماهیت الگوریتم فلوید وارشال
الگوریتم فلوید دارای ماهیت برنامه نویسی پویا می باشد، ابتدا ماتریس مجاورت را به ازای هیچ نود واسطه داریم سپس ماتریس مجاورت را به ازای یک نود واسطه، یعنی فرض کنید رابطه a-c و b-a برقرار باشد به ازای نود واسطه a می توانیم رابطه b-c را نیز برقرار کنیم و یک مرحله الگوریتم را جلو ببریم.
اگر floyd(i,j,k) به ما مقدار کوتاه ترین مسیر نود از i به j با استفاده از k نود اول را برگرداند الگوریتم فلوید بر اساس یک اصل راحت به صورت زیر کار می کند.
floyd(i,j,k)=min(floyd(i,j,k-1),floyd(i,k,k-1)+floyd(k,j,k-1))
الگوریتم بالا فلوید را به صورت یک تابع بازگشتی نشان می دهد که به ازای k=0 برابر با ماتریس اولیه می شود. البته این تکه کد تنها وقتی اضافه میشود که بخواهیم از فلوید برای کوتاه ترین مسیر استفاده کنیم، همانطور که در ادامه می بینید میتوان الگوریتم را با تغییر های کوچک روی مسائل دیگری نیز اعمال کرد. این یک خط بین حالات  استفاده از k به عنوان واسطه و استفاده نکردن از k به عنوان واسطه کمینه را انتخاب می کند. این کار بدیهی هست چون هیچوقت به دنبال طولانی تر کردن یک مسیر با استفاده از یک نود میانی نیستیم بین این دو حالت مینیمم را انتخاب می کنیم. در عمل فلوید را نه به صورت بازگشتی و نه کاملا به صورت پویا پیاده سازی می کنند. ما میتوانیم با داشتن یک ماتریس مجاورت یا ماتریس هزینه و در هر مرحله بروز رسانی همان ماتریس در انتها کوتاه ترین مسیر بین تمامی نود ها را داشته باشیم.
اینکار باعث صرفه جویی در مصرف حافظه می شود اما ماهیت پویا و بازگشتی الگوریتم را از بین می برد. این الگوریتم شبیه حالتی از پویا به صورت tabulation یا از پایین به بالا می شود با این تفاوت که در حال بهتر کردن ارتباط هستیم در برنامه نویسی پویا بهتر کردن یک مقدار معنی ندارد.

پیاده سازی الگوریتم فلوید با حافظه بهینه
در هریک از حالات الگوریتم فلوید که در برنامه نویسی رقابتی مطرح می شود نیاز به یک آرایه دو بعدی برای نشان دادن وجود رابطه بین i یا j یا هزینه برای رسیدن از i یا j داریم. در پیاده سازی این الگوریتم سه حلقه for به طول n پشت سرهم می بینیم و سپس همان خط بخصوص مطرح شده در بالا. توجه کنید که همیشه k (یعنی متغیری که واسطه می شود) باید در بالاترین حلقه تغییر کند وگرنه الگوریتم کامل نیست و به ازای تعدادی از ورودی ها خروجی نادرست به دنبال دارد.

شبه کد حالت کلی الگوریتم فلوید
for(k=0;k<n;k++)
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
            optimise i to j using k

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

سه حالت مسئله مختلف الگوریتم فلوید


پیدا کردن کوتاه ترین مسیر بین تمامی نود ها

اولین حالت الگوریتم فلوید برای بدست آوردن کوتاه ترین مسیر بین تمامی نود هاست، همانطور که می دانید برخلاف سادگی پیاده سازی الگوریتم فلوید دارای پیچیدگی زمانی زیادی برای کامپیوتر است. حتما برای تعداد نود های بیشتر الگوریتم های بهتری مثل دایجسترا و A* و اگر هزینه ارتباط بین نود ها همیشه مقدار ثابت هست BFS را بررسی کنید.
به هر حال خط بهینه ساز الگوریتم فلوید برای پیدا کردن کوتاه ترین به صورت زیر می شود:
cost[i][j]=min(cost[i][j],cost[i][k]+cost[k][j])
برای اینکه الگوریتم به خوبی عمل کند باید هزینه نود هایی که باهم ارتباط ندارند را بی نهایت در نظر بگیریم و چون عددی به اسم بی نهایت در زبان های برنامه نویسی وجود ندارد مقدار بیشینه ای که میتوان برای مثال به int نسبت داد را به هزینه ارتباط نود هایی که باهم ارتباطی ندارند نسبت می دهیم زیرا که هر نوع ارتباط با هر هزینه ای بهتر از ارتباط نداشتن است اگر به طور اشتباه این مقدار را صفر در نظر بگیریم و از آرایه های کمکی نیز استفاده نکنیم هیچوقت بین دو گره که با هم ارتباط ندارند ارتباطی ایجاد نمی شود.

اعمال تعدی روی یک ماتریس مجاورت

ماتریس مجاورت را در یک تعریف خیلی ساده میتوان همان ماتریس یا آرایه دو بعدی هزینه وقتی که 1 به معنی برقرار بودن ارتباط و 0 به معنی برقرار نبودن ارتباط می باشد در نظر گرفت. هدف از اعمال فلوید روی این این ماتریس مجاورت این است که تا حد امکان 0 ها را با استفاده از رابطه تعدی تبدیل به 1 کنیم برای مثال درنظر بگیرید میخواهیم قانون دوست دوست هر شخص دوست آن شخص هست را روی یک ماتریس مجاورت که 1 بودن خانه i و j نشانه دوست بودن است نشان دهیم هدف این است که اگر سعید با مرتضی و مرتضی با علی دوست است به ارتباط دوستی بین سعید و علی برسیم. پیش از این یک مثال از اعمال تعدی در یک پست بلاگ گفته شد.
خط بهینه ساز الگوریتم فلوید برای اعمال تعدی
cost[i][j]=max(cost[i][j],cost[i][k]&&cost[k][j])

پیدا کردن قوی ترین مسیر بین تمامی نود ها
در بعضی از مسائل ارتباط بین گره ها از جنس هزینه نیست بلکه شبیه شبکه جریان در الگوریتم بیشینه جریان می باشد، با این تفاوت که فقط یک مسیر را میتوانیم برداریم، و فقط یک گره شروع و پایانی نداریم و از تمامی گره ها یک مسیر قوی به تمامی گره های دیگر بدست می آوریم.
خط بهینه ساز الگوریتم فلوید برای پیدا کردن قوی ترین مسیر
cost[i][j]=max(cost[i][j],min(cost[i][k],cost[k][j]))

بدست آوردن مسیر

الگوریتم فلوید به این شکل که در بالا مطرح شد میتواند "هزینه جواب" را پیدا کند ولی اطلاعاتی از نود های واسطه به ما نمی دهد، یعتی تنها اینکه از تهران تا لندن 5479 کیلومتر جاده زمینی است را بدست می آورد و اینکه از چه شهرهایی در این مسیر بهینه باید گذشت را به عنوان جواب ندارد.

برای بدست آوردن جواب بهینه همراه با مسیر i به j به یک آرایه دو بعدی به اندازه ماتریس مجاورت نیاز داریم. برای پیاده سازی در این آرایه ابتدا تمامی مقادیر را برابر با -1 قرار می دهیم و سپس در صورتی که از یک گره میانی استفاده شود در خانه مربوط به i و j مقدار k که همان نود میانی می باشد نوشته می شود به این ترتیب برای بدست آوردن مسیر i به j اگر k غیر از -1 بود و مقدار دهی شده بود به طور بازگشتی باید مسیر i تا k را بدست آوریم و این کار را تا جایی ادامه بدهیم که نود واسطه از بین رفته و به یک مسیر مستقیم برسیم، بدیهی است که k هایی که در این بین بدست می آیند همان گره های واسطه با ترتیب برعکس هستند.