الگوریتم فلوید-وارشال کیست؟ توضیح بده.
در علوم کامپیوتر الگوریتم فلوید-وارشال یک الگوریتم تحلیل گراف برای پیدا کردن کوتاهترین مسیر در یک گراف جهت دار و وزن دار می‌باشد. با یکبار اجرای این الگوریتم کوتاه‌ترین مسیر بین همهٔ جفت راس‌ها پیدا خواهد شد. الگوریتم فلوید-وارشال به نام استفن وارشال و رابرت فلوید نامگذاری شده‌است. این الگوریتم یک مثال از برنامه‌نویسی پویا می‌باشد.در این الگوریتم، ابتدا ماتریس مجاورت برای نقاط گراف نوشته شده و در مرحلهٔ بعد با استفاده از یک راس واسطه، کوتاه‌ترین فاصله بین نقاط را محاسبه کرده و ماتریس را با مقادیر جدید بازنویسی می‌کند. پس از آن دو نقطه به عنوان واسطه انتخاب شده و ماتریس جدید به دست می‌آید. با تکرار این روند الگوریتم به پایان رسیده و در نهایت ماتریسی ایجاد شده که کوتاه‌ترین مسیر بین تمامی نقاط را محاسبه کرده‌است. بدیهی است که کوتاه‌ترین مسیر بین مبدأ و مقصد را می‌توان به راحتی از ماتریس تشکیل شده‌استخراج نمود.این الگوریتم برای گراف های با یال منفی، جواب نمی‌دهد.الگوریتم.الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف، بین هر جفت از راس هارا مقایسه می‌کند. این الگوریتم قادر است این کار را تنها با formula_1 مقایسه انجام دهد. این ملاحظه قابل توجهی می‌باشد که در یک گراف formula_2 یال وجود داشته باشد وهر ترکیبی از یالها چک شده باشد. یک گراف formula_3 با راس‌های formula_4 که 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 را در در فرمول بازگشتی زیر ارائه می‌دهیم:formula_5این رابطه قلب الگوریتم وارشال می‌باشد این الگوریتم در اولین محاسبه (ShortestPath(i,j،۱ را برای همهٔ جفت‌های (i ,j) پیدا می‌کند و سپس از این برای پیدا کردن (Shortestpath(i,j،۲ برای همهٔ جفت‌های (i ,j) استفاده می‌شود و این روال تا زمانی که k=N شود ادامه می‌یابد و ما می‌توانیم کوتاهترین مسیر بین جفت‌های (i,j) را با استفاده از راس‌های میانی پیدا کنیم.شبه کد. 1 let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) 2 for each edge ("u","v") 3 dist["u"]["v"] ← w("u","v") "// the weight of the edge ("u","v") 4 for each vertex "v" 5 dist["v"]["v"] ← 0 6 for "k" from 1 to |V| 7 for "i" from 1 to |V| 8 for "j" from 1 to |V| 9 if dist["i"]["j"] &gt; dist["i"]["k"] + dist["k"]["j"] 10 dist["i"]["j"] ← dist["i"]["k"] + dist["k"]["j"] 11 end ifتحلیل.در هر مرحله‌ی برای یافتن تمامی formula_6 مقدار formula_7‌ها (برای formula_8های بزرگ‌تر از ۰ و تمامی formula_9ها) با استفاده از مقادیر formula_10 نیاز به formula_11 عملیات داریم. با توجه به این که ما با مقداردهی اولیه formula_12 شروع می‌کنیم و سپس دنباله‌ٔ formula_13 formula_14, formula_15, formula_16, formula_17 را محاسبه می‌کنیم، مجموع تعداد عملیات‌های مورد نیاز ما برابر با formula_18 خواهد بود. در نتیجه پیجدگی محاسباتی این الگوریتم از formula_19 خواهد بود.تحلیل درستی با یک مثال.در این تصویر مشاهده می کنید که چگونه توسط استخراج ماتریس مجاورت(D0) از گراف روابط وزن دار الگوریتم فلوید وارشال را به صورت دستی در چهار مرحله اعمال کرده ایم.کاربردها.الگوریتم وارشال برای حل مسایل زیر می‌تواند استفاده شود.پیاده‌سازی‌ها.پیاده‌سازی این الگوریتم در زبان‌های برنامه‌نویسی مختلفی وجود دارد.۶- برای متلب در بسته Matlab_bgl۷- برای پایتون در کتابخانه یا کتابخانه ۸- برای R در کتابخانه e1071