AlgoVerse

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

کوتاه‌ترین مسیر بین همه‌ی جفت گره‌ها با برنامه‌ریزی پویا: گره‌ها یکی‌یکی به‌عنوان ایستگاه میانی مجاز می‌شوند.

می‌خواهیم کوتاه‌ترین فاصله‌ی همه‌ی جفت‌ها را داشته باشیم. Floyd–Warshall یک برنامه‌ریزی پویای ساده است:

ادامه‌ی توضیح ↓
ورودی:
V=5 · E=9 · src=1خروجی PDF

پنج گره با دو یال منفی و بدون دور منفی؛ اعداد کنار گره‌ها فاصله از گره‌ی ۱ هستند.

  1. INF = float("inf")
  4. def floyd_warshall(graph, src):
  5. dist = {u: {v: INF for v in graph} for u in graph}
  6. for u in graph:
  7. dist[u][u] = 0
  8. for v, w in graph[u]:
  9. dist[u][v] = min(dist[u][v], w)
  10. from_src = dist[src]
  11. for k in graph:
  12. row_k = dist[k]
  13. for i in graph:
  14. if dist[i][k] == INF:
  15. continue
  16. for j in graph:
  17. if dist[i][k] + row_k[j] < dist[i][j]:
  18. dist[i][j] = dist[i][k] + row_k[j]
  19. for v in graph:
  20. if dist[v][v] < 0:
  21. return None
  22. return dist

ناوردا: بعد از دور k، dist[i][j] طول کوتاه‌ترین مسیری از i به j است که ایستگاه‌های میانی‌اش فقط از گره‌های تا k باشد.

شروع اجرا

38-41742-5612345
  • گره‌ی جاری (k)
  • درخت کوتاه‌ترین مسیر تا اینجا
  • یالِ در حال بررسی

متغیرهای محلی

src'1'

نارنجی = در همین گام عوض شد

graph dict
  • '1': [('2', 3), ('3', 8), ('5', -4)]
  • '2': [('4', 1), ('5', 7)]
  • '3': [('2', 4)]
  • '4': [('1', 2), ('3', -5)]
  • '5': [('4', 6)]

Call stack

  1. floyd_warshall()خط 4
گام ۱ از ۳۴۸
خط سیاه = via · خط نارنجی = گام کلیدیcompare: 0/95 · init: 0/1 · via: 0/5 · shorten: 0/18 · cycle_check: 0/5

    رشد تعداد عملیات با اندازه‌ی ورودی

    میانگین ۵ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

    • comparisons
    • ورودی فعلی (n=5)
    02004006004812n = تعداد گره‌هاcomparisons
    نمایش به شکل جدول
    ncomparisons
    439.2
    8244.8
    12583.2
    توضیح

    ایده

    می‌خواهیم کوتاه‌ترین فاصله‌ی همه‌ی جفت‌ها را داشته باشیم. Floyd–Warshall یک برنامه‌ریزی پویای ساده است:

    dist[i][j] در دور k = کوتاه‌ترین مسیر از i به j که ایستگاه‌های میانی‌اش فقط از گره‌های اول تا k باشند.

    در دور k برای هر جفت می‌پرسیم: آیا رفتن از راه k بهتر است؟

    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    نکته‌ها

    • با یال منفی کار می‌کند. اگر در پایان dist[v][v] < 0 شود، v روی یک دور منفی است.
    • سه حلقه‌ی تودرتو: O(V³)؛ کد بسیار کوتاه است و برای گراف‌های کوچک و پر از یال مناسب است.
    • k باید بیرونی‌ترین حلقه باشد؛ اگر جای حلقه‌ها عوض شود، جواب غلط می‌شود.

    در trace به چه چیزی نگاه کنی

    • عدد کنار هر گره فاصله از گره‌ی اول است (یک ردیف ماتریس)؛ کل ماتریس dist در پنل حافظه است.
    • گره‌ی برجسته k است، یعنی ایستگاه میانی این دور.