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

از ویکی‌پدیا، دانشنامهٔ آزاد
پرش به: ناوبری، جستجو

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

الگوریتم[ویرایش]

الگوریتم وارشال همهٔ مسیرهای ممکن در یک گراف، بین هر جفت از راس هارا مقایسه می‌کند. این الگوریتم قادر است این کار را تنها با 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 موجود می‌باشد

پانویس[ویرایش]

  1. Stephen Warshall
  2. Robert Floyd

منابع[ویرایش]