الگوریتم وارشال:
الگوريتم وارشال:وریتم فلوید-وارشال یک الگوریتم تحلیل گراف برای پیدا کردن کوتاهترین مسیر در یگ گراف جهتدار و وزن دار میباشد .با یکبار اجرای این الگوریتم کوتاهترین مسیر بین همهٔ جفت راسها پیدا خواهد شد. الگوریتم فلوید-وارشال به نام استفن وارشال [۱] و روبرت فلوید [۲] نامگذاری شدهاست. این الگوریتم یک مثال از برنامه نویسی پویا میباشد.
الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف , بین هر جفت از راس هارا مقایسه میکند. این الگوریتم قادر است این کار را تنها با V2 مقایسه انجام دهد. این ملاحظه قابل توجهی میباشد که در یک گراف V2 یال وجود داشته باشد وهر ترکیبی از یالها چک شده باشد. یک گراف G با راسهای Vi که i از 1 تا N میباشد را در نظر بگیرید. علاوه بر این یک تابع به نام (shortestPath(i,j,k را در نظر بگیرید که کوتاهترین مسیر ممکن از i تا j را با استفاده از راسهای 1 تا k که به عنوان راسهای میانی در امتداد مسیر میباشند را بر میگرداند.
هم اکنون این تابع داده شدهاست .هدف ما پیدا کردن کوتاهترین مسیر از هر i تا هر j تنها با استفاده از راسهای 1 تا 1+k میباشد. دو کاندیدا برای این مسیر وجود دارد :
1-کوتاهترین مسیری که فقط از راسهای موجود در مجموعه ی(k,........,1) استفاده میکند.
2-تعدادی مسیر که از i تا 1+k و سپس از 1+k تا j میروند وجود دارد که این مسیر بهتر میباشد.