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

الگوریتم فلوید-وارشال
کلاسمسئله یافتن کوتاهترین مسیر (for weighted graphs)
ساختمان دادهگراف (ساختار داده)
کارایی بدترین حالت
کارایی بهترین حالت
کارایی متوسط
پیچیدگی محاسباتی بدترین حالت

در علوم کامپیوتر الگوریتم فلوید-وارشال (به انگلیسی: Floyd–Warshall algorithm) یک الگوریتم تحلیل گراف برای پیدا کردن کوتاهترین مسیر در یک گراف جهت دار و وزن دار می‌باشد. با یکبار اجرای این الگوریتم کوتاه‌ترین مسیر بین همهٔ جفت راس‌ها پیدا خواهد شد. الگوریتم فلوید-وارشال به نام استفن وارشال[۱] و روبرت فلوید[۲] نامگذاری شده‌است. این الگوریتم یک مثال از برنامه‌نویسی پویا می‌باشد.در این الگوریتم، ابتدا ماتریس مجاورت برای نقاط گراف نوشته شده و در مرحلهٔ بعد با استفاده از یک راس واسطه، کوتاه‌ترین فاصله بین نقاط را محاسبه کرده و ماتریس را با مقادیر جدید بازنویسی می‌کند. پس از آن دو نقطه به عنوان واسطه انتخاب شده و ماتریس جدید به دست می‌آید. با تکرار این روند الگوریتم به پایان رسیده و در نهایت ماتریسی ایجاد شده که کوتاه‌ترین مسیر بین تمامی نقاط را محاسبه کرده‌است. بدیهی است که کوتاه‌ترین مسیر بین مبدأ و مقصد را می‌توان به راحتی از ماتریس تشکیل شده‌استخراج نمود.

زبان های دیگر