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

پیمایش گراف و پیمایش درخت
هرس آلفا بتا A* B* Beam الگوریتم بلمن–فورد Best-first Bidirectional الگوریتم جستجوی اول سطح D* الگوریتم جستجوی عمق اول Depth-limited الگوریتم دیکسترا الگوریتم فلوید-وارشال الگوریتم تپه‌نوردی جستجوی عمق اول عمیق‌کننده تکراری الگوریتم جانسون Lexicographic breadth-first Uniform-cost رده:الگوریتم‌های جستجو
جستار وابسته
برنامه‌ریزی پویا Search games

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

الگوریتم

الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف، بین هر جفت از راس هارا مقایسه می‌کند. این الگوریتم قادر است این کار را تنها با $V^3$ مقایسه انجام دهد. این ملاحظه قابل توجهی می‌باشد که در یک گراف $V^2$ یال وجود داشته باشد وهر ترکیبی از یالها چک شده باشد. یک گراف $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 می‌روند وجود دارد که این مسیر بهتر می‌باشد.

ما می‌دانیم که بهترین مسیر از i تا j که فقط از راس‌های بین 1 تا k+1 استفاده می‌کند توسط (ShortestPath(i,j,k تعریف شده‌است و واضح است که اگر یک مسیر بهتر از i تا1+k و از 1+k تا j وجود داشته باشد بنابراین طول مسیربین i,j ازالحاق کوتاهترین مسیر از i تا 1+k و کوتاهترین مسیر از 1+k تا j بدست می‌آید.بنابراین تابع ( ShortestPath(i,j,k را در در فرمول بازگشتی زیر ارائه می‌دهیم:

$\textrm{shortestPath}(i,j,k) = \min(\textrm{shortestPath}(i,j,k-1),\textrm{shortestPath}(i,k,k-1)\,+\,\textrm{shortestPath}(k,j,k-1));\,\!$

این رابطه قلب الگوریتم وارشال می‌باشد این الگوریتم در اولین محاسبه ( ShortestPath(i,j,1 را برای همهٔ جفت‌های (i ,j) پیدا می‌کند و سپس از این برای پیدا کردن (Shortestpath(i,j,2 برای همهٔ جفت‌های (i ,j ) استفاده می‌شود و این روال تا زمانی که k=N شود ادامه می‌یابد و ما می‌توانیم کوتاهترین مسیر بین جفت‌های (i,j) رابا استفاده از راس‌های میانی پیدا کنیم.

شبه کد

1 /* Assume a function edgeCost(i,j) which returns the cost of the edge from i to j
 2    (infinity if there is none).
 3    Also assume that n is the number of vertices and edgeCost(i,i)=0
 4 */
 5
 6 int path[][];
 7 /* A 2-dimensional matrix. At each step in the algorithm, path[i][j] is the shortest path
 8    from i to j using intermediate vertices (1..k-1).  Each path[i][j] is initialized to
 9    edgeCost(i,j) or infinity if there is no edge between i and j.
10 */
11
12 procedure FloydWarshall ()
13    for $\mathit{k} := 1$ to $\mathit{n}$
14       for each $\mathit{(i,j)}$ in $\lbrace 1,..,n \rbrace^2$
15          path[i][j] = min ( path[i][j], path[i][k]+path[k][j] );

تحلیل

برای پیدا کردن همه$\mathit{n}^2$ تا $\mathcal{W}_k(i,j)$(یک است اگر بین i,j راسی بزرگتر از k نباشد در غیر این صورت صفر می‌باشد.) از $\mathcal{W}_{\mathit{k}-1(i ,j)}$ به $2\mathit{n}^2$ بیت عملیات نیاز داریم. برای اینکه ما با $\mathcal{W}_0 = \mathcal{W}_\mathcal{R}$ شروع می‌کنیم و n ماتریس صفر و یک

$\mathcal{W}_1$, $\mathcal{W}_2$, $...$, $\mathcal{W}_\mathit{n} = \mathcal{M}_{\mathcal{R}^*}$

را محاسبه می‌کنیم.در نتیجه جمع بیت عملیات‌هایی که استفاده کردیم برابر با$\mathit{n} \times 2\mathit{n}^2 = 2\mathit{n}^3$ می‌باشد.بنابراین پیچیدگی الگوریتم از (Θ(n^3 باشد.

کاربردها

الگوریتم وارشال برای حل مسایل زیر می‌تواند استفاده شود.

1-کوتاهترین مسیرها در گراف‌های جهت دار

2-بستار متعدی گراف‌های جهت دار

3-در فرمول عمومی الگوریتم وارشال گراف بی وزن می‌باشد و توسط یک ماتریس مجاورت نمایش داده شده‌است.

4- وارون سازی یک ماتریس حقیقی

5- تست کردن اینکه آیا یک گراف بی جهت، دو قسمتی می‌باشد یا خیر.

6-محاسبه سریع شبکه‌های راه یاب

پیاده سازی‌ها

1- یک پیاده سازی Perl در مدل گراف موجود می‌باشد.

2- یک پیاده سازی javascript در Alex Le's Blog موجود می‌باشد.

3- یک پیاده سازی C در ece.rice.edu موجود می‌باشد.

4- یک پیاده سازی جاوا در کتابخانهٔ Apache commons graph موجود می‌باشد.

5- یک پیاده سازی با زبان #C در QuickGraph موجود می‌باشد

منابع

• مقدمه‌ای بر الگوریتم‌ها - پدیدآورنده: تامس کورمن، چارلز لیزرسان، رونالد دیوست، کلیفورد اشتاین - گروه مهندسی-پژوهشی خوارزمی (مترجم) - ناشر: درخشش
• ویکی‌پدیای انگلیسی