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

چرا کوتاه‌ترین مسیرهای وزن‌دار به تکنیک‌های جدید نیاز دارند

جستجوی سطح‌اول، که پیش‌تر در این مجموعه بحث شد، کوتاه‌ترین مسیرها را با شمردن یال‌ها پیدا می‌کند، که وقتی هر یال همان وزن ضمنی ۱ را داشته باشد کاملاً کار می‌کند. وقتی یال‌ها وزن‌های متفاوتی دارند، که نشان‌دهنده فاصله‌ها، هزینه‌ها، یا زمان‌هاست، یک رویکرد متفاوت نیاز است، و امکان وزن‌های یال منفی پیچیدگی‌های واقعی معرفی می‌کند که BFS هرگز مجبور به در نظر گرفتن آن‌ها نبود.

تکنیک اصلی: Relaxation

هر الگوریتم کوتاه‌ترین‌مسیر در این مقاله روی همان عملیات بنیادین، Relaxation، ساخته می‌شود: برای یک یال (u, v) با وزن w، بررسی کن آیا عبور از u مسیر کوتاه‌تری به v نسبت به بهترین مسیر شناخته‌شده فعلی ارائه می‌دهد، و اگر چنین است، فاصله ثبت‌شده و اسلاف v را به‌روزرسانی کن.

RELAX(u, v, w):
  اگر v.d > u.d + w(u, v):
      v.d = u.d + w(u, v)
      v.p = u

هر رأس با d = infinity شروع می‌شود (به‌جز منبع، که با ۰ شروع می‌شود)، و الگوریتم‌ها عمدتاً در ترتیبی که relaxation را در سراسر یال‌های گراف اعمال می‌کنند متفاوت‌اند.

الگوریتم بلمن-فورد: مدیریت وزن‌های منفی

Bellman-Ford الگوریتم عمومی‌تری است، که حتی وقتی وزن‌های یال منفی باشند به‌درستی کار می‌کند، و می‌تواند به‌طور اضافی وجود یک Negative-Weight Cycle (چرخه با وزن منفی) دسترس‌پذیر از منبع را تشخیص دهد — وضعیتی که در آن کوتاه‌ترین مسیرها حتی به‌خوبی تعریف‌شده نیستند، چون می‌توان به‌طور نامحدود دور چرخه منفی چرخید تا مسیر را به‌طور دلخواه کوتاه کرد.

BELLMAN-FORD(G, w, s):
  INITIALIZE-SINGLE-SOURCE(G, s)
  برای i = 1 تا |G.V| - 1:
      برای هر یال (u, v) در G.E:
          RELAX(u, v, w)
  برای هر یال (u, v) در G.E:
      اگر v.d > u.d + w(u, v):
          FALSE را برگردان      // چرخه با وزن منفی تشخیص داده شد
  TRUE را برگردان

الگوریتم صرفاً هر یال در گراف را، تکرارشده |V| - 1 بار، relax می‌کند. این تعداد تکرار دلخواه نیست: یک کوتاه‌ترین مسیر در یک گراف با V رأس می‌تواند حداکثر V-1 یال داشته باشد (با فرض عدم وجود چرخه‌های منفی، چون مسیری که دوبار از یک رأس بازدید کند نمی‌تواند کوتاه‌ترین باشد)، پس پس از V-1 دور relax‌کردن هر یال، هر کوتاه‌ترین مسیری تضمین می‌شود کاملاً منتشر شده باشد، صرف‌نظر از اینکه یال‌ها در چه ترتیبی در نظر گرفته شده باشند.

تشخیص چرخه‌های منفی

حلقه نهایی بررسی می‌کند آیا هر یالی همچنان می‌تواند پس از V-1 دور relax شود. اگر چنین باشد، این یعنی برخی مسیر همچنان پس از بیشتر از یال‌هایی که هر کوتاه‌ترین‌مسیر غیرچرخه‌ای احتمالاً به آن‌ها نیاز داشت در حال بهبود است، که فقط ممکن است اگر یک چرخه با وزن منفی در جایی دسترس‌پذیر از منبع وجود داشته باشد.

از آنجا که الگوریتم V-1 دور اجرا می‌کند، هرکدام هر یال را بررسی می‌کنند، بلمن-فورد در زمان O(VE) اجرا می‌شود — به‌طور محسوسی کندتر از الگوریتم‌هایی که در ادامه می‌آیند، اما هروقت وزن‌های منفی ممکن باشند ضروری است.

الگوریتم دیجکسترا: سریع‌تر، اما بدون مجوز وزن‌های منفی

وقتی همه وزن‌های یال تضمین‌شده غیرمنفی باشند، Dijkstra's Algorithm (الگوریتم دیجکسترا) یک راه‌حل به‌طور قابل‌توجه سریع‌تر با پردازش رأس‌ها به یک ترتیب حریصانه خاص، با استفاده از ساختار صف اولویت که پیش‌تر در این مجموعه درباره هیپ‌ها بحث شد، ارائه می‌دهد.

DIJKSTRA(G, w, s):
  INITIALIZE-SINGLE-SOURCE(G, s)
  S = مجموعه خالی          // رأس‌هایی که فاصله نهایی‌شان تعیین شده
  Q = صف اولویت حاوی همه رأس‌ها، کلیددهی‌شده با .d
  تا زمانی که Q خالی نباشد:
      u = EXTRACT-MIN(Q)
      S = S ∪ {u}
      برای هر v در Adj[u]:
          RELAX(u, v, w)  // این ممکن است DECREASE-KEY را روی v در Q اعمال کند

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

چرا وزن‌های غیرمنفی برای درستی ضروری‌اند

درستی دیجکسترا به یک ادعای حریصانه متکی است: وقتی یک رأس از صف اولویت استخراج شود (به S اضافه شود)، مقدار فاصله‌اش تضمین می‌شود کوتاه‌ترین فاصله واقعی‌اش باشد و هرگز نیاز به به‌روزرسانی دوباره نخواهد داشت. این ادعا به‌طور حیاتی به وزن‌های غیرمنفی بستگی دارد: اگر یک یال منفی وجود داشت، یک مسیر از میان یک رأس هنوز-نه-در S می‌توانست بالقوه همچنان یک مسیر کوتاه‌تر به یک رأس از‌قبل-نهایی‌شده تولید کند، که فرض حریصانه را کاملاً نقض می‌کند. این دقیقاً چرایی این است که الگوریتم دیجکسترا نتایج نادرست تولید می‌کند اگر وزن‌های یال منفی به آن داده شود، بدون هیچ هشداری که چیزی اشتباه رفته است.

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

با استفاده از یک هیپ دودویی برای صف اولویت:
V فراخوانی EXTRACT-MIN، هرکدام هزینه O(log V)
E فراخوانی DECREASE-KEY (از طریق relaxation)، هرکدام هزینه O(log V)

مجموع: O((V + E) log V)

با استفاده از یک هیپ فیبوناچی (که پیش‌تر در این مجموعه
درباره درخت‌های پوشای کمینه ذکر شد):
DECREASE-KEY هزینه O(1) مستهلک به‌جای O(log V) دارد

مجموع: O(V log V + E)

نوع هیپ فیبوناچی از نظر مجانبی برای گراف‌های چگال سریع‌تر است، هرچند نسخه هیپ دودویی برای پیاده‌سازی ساده‌تر است و اغلب در عمل به‌دلیل فاکتورهای ثابت کوچک‌تر سریع‌تر است.

مقایسه دو الگوریتم

بلمن-فورد:
  - وزن‌های یال منفی را به‌درستی مدیریت می‌کند
  - چرخه‌های وزن-منفی را تشخیص می‌دهد
  - زمان اجرا: O(VE) — کندتر

الگوریتم دیجکسترا:
  - نیازمند همه وزن‌های یال غیرمنفی است
  - نمی‌تواند چرخه‌های منفی را تشخیص یا مدیریت کند
  - زمان اجرا: O((V+E) log V) یا O(V log V + E) — سریع‌تر

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

چرا کوتاه‌ترین مسیرهای منبع واحد در بسیاری حوزه‌ها اهمیت دارند

این الگوریتم‌ها زیربنای سیستم‌های ناوبری GPS که مسیرهای رانندگی را محاسبه می‌کنند، پروتکل‌های مسیریابی شبکه که تعیین می‌کنند بسته‌های داده چگونه در سراسر اینترنت سفر می‌کنند، و بی‌شمار