الگوریتم فلوید-وارشال: یافتن کوتاه‌ترین مسیرها بین هر جفت رأس

مسئله کوتاه‌ترین مسیرهای همه‌جفت

الگوریتم‌های منبع-واحد که پیش‌تر در این مجموعه بحث شدند، بلمن-فورد و الگوریتم دیجکسترا، کوتاه‌ترین مسیرها را از یک رأس منبع خاص به هر رأس دیگر پیدا می‌کنند. مسئله All-Pairs Shortest Paths (کوتاه‌ترین مسیرهای همه‌جفت) چیزی جامع‌تر می‌خواهد: کوتاه‌ترین فاصله بین هر جفت رأس مرتب ممکن در گراف.

یک رویکرد ساده: اجرای مکرر دیجکسترا

واضح‌ترین راه‌حل یک الگوریتم منبع-واحد را یک‌بار از هر رأس به‌عنوان منبع اجرا می‌کند. با استفاده از الگوریتم دیجکسترا، که پیش‌تر در این مجموعه بحث شد، برای هرکدام از V رأس به‌عنوان یک منبع، زمان اجرای کل O(V · (E + V log V)) با استفاده از یک هیپ فیبوناچی می‌دهد، که به O(V² log V + VE) ساده می‌شود. این برای گراف‌های بدون وزن‌های منفی خوب کار می‌کند، اما اگر وزن‌های منفی حاضر باشند، الگوریتم دیجکسترا نمی‌تواند استفاده شود، و اجرای بلمن-فورد از هر منبع به‌جای آن O(V²E) می‌دهد، که برای گراف‌های چگال به O(V⁴) تبدیل می‌شود — کاملاً کند.

الگوریتم فلوید-وارشال: یک رویکرد مستقیم برنامه‌نویسی پویا

به‌جای اجرای مکرر یک الگوریتم منبع-واحد، Floyd-Warshall مسئله همه‌جفت را مستقیماً با استفاده از برنامه‌نویسی پویا، که پیش‌تر در این مجموعه بحث شد، حل می‌کند، و وزن‌های یال منفی را به‌درستی مدیریت می‌کند، هرچند نه چرخه‌های منفی.

تعریف زیرمسئله

بینش کلیدی در نظر گرفتن مسیرهایی است که با کدام رأس‌های میانی می‌توانند از میان آن‌ها عبور کنند محدود شده‌اند. فرض کن d_{ij}^{(k)} کوتاه‌ترین فاصله از رأس i به رأس j باشد، با استفاده فقط از رأس‌های {1, 2, ..., k} به‌عنوان توقف‌های میانی ممکن در طول مسیر.

d_{ij}^{(0)} = w(i, j)     اگر یال (i,j) وجود داشته باشد
             = infinity    در غیر این صورت
             = 0           اگر i == j

برای k ≥ 1، رابطه بازگشتی در نظر می‌گیرد
آیا مسیر بهینه از رأس k به‌عنوان یک
توقف میانی استفاده می‌کند یا نه:

d_{ij}^{(k)} = min(
    d_{ij}^{(k-1)},                        // از رأس k استفاده نکن
    d_{ik}^{(k-1)} + d_{kj}^{(k-1)}        // از رأس k استفاده کن
)

این رابطه بازگشتی می‌گوید: کوتاه‌ترین مسیر از i به j که اجازه استفاده از رأس‌های تا k را دارد یا واقعاً اصلاً از رأس k استفاده نمی‌کند (در این صورت برابر با کوتاه‌ترین مسیر محدودشده به رأس‌های تا k-1 است)، یا دقیقاً یک‌بار از رأس k عبور می‌کند (در این صورت به کوتاه‌ترین مسیر از i به k، به‌علاوه کوتاه‌ترین مسیر از k به j، هر دو محدودشده به رأس‌های میانی تا k-1، تقسیم می‌شود).

پیاده‌سازی الگوریتم

FLOYD-WARSHALL(W, n):
  D⁽⁰⁾ = W    // با وزن‌های یال مستقیم مقداردهی اولیه کن
  برای k = 1 تا n:
      فرض کن D⁽ᵏ⁾ یک ماتریس جدید n × n باشد
      برای i = 1 تا n:
          برای j = 1 تا n:
              D⁽ᵏ⁾[i][j] = min(D⁽ᵏ⁻¹⁾[i][j],
                                D⁽ᵏ⁻¹⁾[i][k] + D⁽ᵏ⁻¹⁾[k][j])
  D⁽ⁿ⁾ را برگردان

در عمل، این با استفاده از یک ماتریس واحد که درجا به‌روزرسانی می‌شود پیاده‌سازی می‌شود، چون هر ورودی فقط به مقادیر از تکرار فعلی یا قبلی به شیوه‌ای که این ساده‌سازی را بدون تأثیر بر درستی اجازه می‌دهد، بستگی دارد.

ردیابی یک مثال کوچک

ماتریس وزن اولیه (∞ یعنی بدون یال مستقیم):
      1    2    3
1  [  0    3    ∞  ]
2  [  ∞    0    1  ]
3  [  2    ∞    0  ]

پس از در نظر گرفتن رأس 1 به‌عنوان میانی:
(بررسی اینکه آیا عبور از 1 هر جفتی را بهبود می‌دهد)
3→2 از طریق 1: 3[1] + 1[2] = 2 + 3 = 5، اما فعلی ∞ است، پس به‌روزرسانی کن

پس از در نظر گرفتن رأس 2 به‌عنوان میانی:
1→3 از طریق 2: 1[2] + 2[3] = 3 + 1 = 4، فعلی ∞ است، پس به‌روزرسانی کن

پس از در نظر گرفتن رأس 3 به‌عنوان میانی:
2→1 از طریق 3: 2[3] + 3[1] = 1 + 2 = 3، فعلی ∞ است، پس به‌روزرسانی کن

ماتریس نهایی کوتاه‌ترین مسیر بین هر جفت را شامل می‌شود

تحلیل زمان اجرا

الگوریتم از سه حلقه تودرتو تشکیل شده، هرکدام n بار اجرا می‌شوند، با کار O(1) درون درونی‌ترین حلقه، که زمان اجرای کل Θ(V³) می‌دهد. این به‌طور قابل‌توجه ساده برای پیاده‌سازی است — فقط سه حلقه تودرتو با یک مقایسه واحد — و به هیچ ساختار داده پیچیده‌ای مانند صف‌های اولویت مورد نیاز الگوریتم دیجکسترا بستگی ندارد.

مقایسه فلوید-وارشال با اجراهای مکرر منبع-واحد

فلوید-وارشال: Θ(V³)، همیشه، وزن‌های منفی را مدیریت می‌کند
دیجکسترای مکرر: O(V² log V + VE)، سریع‌تر برای گراف‌های تنک،
                    اما نمی‌تواند وزن‌های منفی را مدیریت کند
بلمن-فورد مکرر: O(V²E)، که برای گراف‌های چگال به O(V⁴) تبدیل می‌شود،
                    وزن‌های منفی را مدیریت می‌کند اما کندتر
                    از فلوید-وارشال برای گراف‌های چگال است

برای گراف‌های چگال (جایی که E نزدیک به V² است)، Θ(V³) فلوید-وارشال قابل‌مقایسه با یا بهتر از جایگزین‌هاست، و سادگی پیاده‌سازی‌اش، همراه با مدیریت درست وزن‌های منفی بدون نیاز به بلمن-فورد پیچیده‌تر که V بار تکرار می‌شود، آن را به انتخاب عملی تبدیل می‌کند هروقت گراف بسیار تنک نباشد.

تشخیص چرخه‌های منفی با فلوید-وارشال

مشابه با اینکه بلمن-فورد، که پیش‌تر در این مجموعه بحث شد، چرخه‌های منفی را با بررسی بهبود بیشتر پس از پایان حلقه اصلی‌اش تشخیص می‌دهد، فلوید-وارشال یک چرخه با وزن-منفی را با بررسی قطر ماتریس فاصله نهایی تشخیص می‌دهد: اگر هر D[i][i] پس از تکمیل الگوریتم منفی باشد، این یعنی یک مسیر از رأس i به خودش با وزن کل منفی وجود دارد — یک چرخه منفی که از میان i عبور می‌کند.

بازسازی مسیرهای واقعی

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

چرا سادگی فلوید-وارشال یک قوت واقعی است

فراتر از زمان اجرای رقابتی‌اش برای گراف‌های چگال، سادگی پیاده‌سازی فلوید-وارشال — یک حلقه سه‌گانه مستقیم بدون هیچ ساختار داده کمکی — آن را بسیار کمتر مستعد خطا برای پیاده‌سازی درست در مقایسه با اجرای مکرر یک الگوریتم مبتنی بر صف اولویت از هر منبع می‌کند. این بخشی از دلیلی است که چرا فلوید-وارشال یک ابزار استاندارد برای مسائل کوتاه‌ترین مسیر همه‌جفت در عمل باقی می‌ماند، به‌ویژه برای گراف‌های چگال با اندازه متوسط جایی که زمان اجرای مکعبی‌اش کاملاً عملی باقی می‌ماند.