الگوریتم مسیریابی فلوید وارشال (Floyd-Warshall)

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

مثال : کوتاه ترین فواصل در شکل زیر به این صورت محاسبه می شوند.

ابتدا ماتریس مجاورت را تشکیل می دهیم:

سپس با واسطه قرار دادن راس 1 ماتریس را به شیوه ی زیر به هنگام می کنیم:

با ادامه ی این روند به جواب زیر می رسیم:

مطالب مرتبط:

الگوریتم های مسیریابی – بخش اول (الگوریتم دیکسترا) الگوریتم های مسیریابی – بخش سوم (الگوریتم بلمن فورد) الگوریتم های مسیریابی – بخش پنجم و پایانی (ژنتیک)