در علوم کامپیوتر الگوریتم فلوید - وارشال ( به انگلیسی: Floyd–Warshall algorithm ) یک الگوریتم تحلیل گراف برای پیدا کردن کوتاهترین مسیر در یک گراف جهت دار و وزن دار می باشد. با یکبار اجرای این الگوریتم کوتاه ترین مسیر بین همهٔ جفت راس ها پیدا خواهد شد. الگوریتم فلوید - وارشال به نام استفن وارشال و رابرت فلوید نامگذاری شده است. این الگوریتم یک مثال از برنامه نویسی پویا می باشد. در این الگوریتم، ابتدا ماتریس مجاورت برای نقاط گراف نوشته شده و در مرحلهٔ بعد با استفاده از یک راس واسطه، کوتاه ترین فاصله بین نقاط را محاسبه کرده و ماتریس را با مقادیر جدید بازنویسی می کند. پس از آن دو نقطه به عنوان واسطه انتخاب شده و ماتریس جدید به دست می آید. با تکرار این روند الگوریتم به پایان رسیده و در نهایت ماتریسی ایجاد شده که کوتاه ترین مسیر بین تمامی نقاط را محاسبه کرده است. بدیهی است که کوتاه ترین مسیر بین مبدأ و مقصد را می توان به راحتی از ماتریس تشکیل شده استخراج نمود.
این الگوریتم برای گراف های با یال منفی، جواب نمی دهد.
الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف، بین هر جفت از راس هارا مقایسه می کند. این الگوریتم قادر است این کار را تنها با V 3 مقایسه انجام دهد. این ملاحظه قابل توجهی می باشد که در یک گراف V 2 یال وجود داشته باشد وهر ترکیبی از یالها چک شده باشد. یک گراف G با راس های V i که i از ۱ تا N می باشد را در نظر بگیرید. علاوه بر این یک تابع به نام ( shortestPath ( i, j، k را در نظر بگیرید که کوتاهترین مسیر ممکن از i تا j را با استفاده از راس های ۱ تا k که به عنوان راسهای میانی در امتداد مسیر می باشند را برمی گرداند.
هم اکنون این تابع داده شده است. هدف ما پیدا کردن کوتاهترین مسیر از هر i تا هر j تنها با استفاده از راسهای ۱ تا 1+k می باشد. دو کاندیدا برای این مسیر وجود دارد:
۱ - کوتاهترین مسیری که فقط از راس های موجود در مجموعه ی ( k, . . . . . . . . , 1 ) استفاده می کند.
۲ - تعدادی مسیر که از i تا 1+k و سپس از 1+k تا j می روند وجود دارد که این مسیر بهتر می باشد.
ما می دانیم که بهترین مسیر از i تا j که فقط از راس های بین ۱ تا k+1 استفاده می کند توسط ( ShortestPath ( i, j، k تعریف شده است و واضح است که اگر یک مسیر بهتر از i تا1+k و از 1+k تا j وجود داشته باشد بنابراین طول مسیر بین i, j از الحاق کوتاهترین مسیر از i تا 1+k و کوتاهترین مسیر از 1+k تا j بدست می آید؛ بنابراین تابع ( ShortestPath ( i, j، k را در در فرمول بازگشتی زیر ارائه می دهیم:
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفاین الگوریتم برای گراف های با یال منفی، جواب نمی دهد.
الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف، بین هر جفت از راس هارا مقایسه می کند. این الگوریتم قادر است این کار را تنها با V 3 مقایسه انجام دهد. این ملاحظه قابل توجهی می باشد که در یک گراف V 2 یال وجود داشته باشد وهر ترکیبی از یالها چک شده باشد. یک گراف G با راس های V i که i از ۱ تا N می باشد را در نظر بگیرید. علاوه بر این یک تابع به نام ( shortestPath ( i, j، k را در نظر بگیرید که کوتاهترین مسیر ممکن از i تا j را با استفاده از راس های ۱ تا k که به عنوان راسهای میانی در امتداد مسیر می باشند را برمی گرداند.
هم اکنون این تابع داده شده است. هدف ما پیدا کردن کوتاهترین مسیر از هر i تا هر j تنها با استفاده از راسهای ۱ تا 1+k می باشد. دو کاندیدا برای این مسیر وجود دارد:
۱ - کوتاهترین مسیری که فقط از راس های موجود در مجموعه ی ( k, . . . . . . . . , 1 ) استفاده می کند.
۲ - تعدادی مسیر که از i تا 1+k و سپس از 1+k تا j می روند وجود دارد که این مسیر بهتر می باشد.
ما می دانیم که بهترین مسیر از i تا j که فقط از راس های بین ۱ تا k+1 استفاده می کند توسط ( ShortestPath ( i, j، k تعریف شده است و واضح است که اگر یک مسیر بهتر از i تا1+k و از 1+k تا j وجود داشته باشد بنابراین طول مسیر بین i, j از الحاق کوتاهترین مسیر از i تا 1+k و کوتاهترین مسیر از 1+k تا j بدست می آید؛ بنابراین تابع ( ShortestPath ( i, j، k را در در فرمول بازگشتی زیر ارائه می دهیم:
wiki: الگوریتم فلوید وارشال