الگوریتم های مسیریابی – بخش چهارم (فلوید وارشال)

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

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

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

11 thumb الگوریتم های مسیریابی   بخش چهارم (فلوید وارشال)

 

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

12 thumb الگوریتم های مسیریابی   بخش چهارم (فلوید وارشال)

 

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

 

13 thumb الگوریتم های مسیریابی   بخش چهارم (فلوید وارشال)

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

14 thumb الگوریتم های مسیریابی   بخش چهارم (فلوید وارشال)

Как пользователя, меня это обстоятельство радует, а вот как оптимизатора – не очень topodin,

مطالب مرتبط

نظر بدهید

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *