الگوریتمهای کوتاهترین مسیر
الگوریتمهای کوتاهترین مسیر، کوتاهترین مسیرها را بین رئوس در یک گراف وزندار محاسبه میکنند. الگوریتمهای مختلفی برای وزنهای نامنفی، وزنهای منفی، و جستجوهای همه جفتها در مقابل تک منبع مناسب هستند.
Definition
کوتاهترین مسیر بین دو رأس در یک گراف وزندار، مسیری است که مجموع وزن یالهای آن حداقل باشد؛ الگوریتمهای کوتاهترین مسیر، چنین مسیرها و فواصل آنها را محاسبه میکنند، چه از یک منبع به همه رئوس و چه بین همه جفت رئوس.
Scope
این موضوع شامل کوتاهترین مسیرهای تک منبع (الگوریتم دایکسترا برای وزنهای نامنفی، بلمن-فورد برای گرافهای با وزنهای منفی و برای تشخیص چرخههای منفی)، کوتاهترین مسیرهای همه جفتها (فلوید-وارشال، الگوریتم جانسون)، و کوتاهترین مسیرها در گرافهای جهتدار بدون دور است. این موضوع به اصل ریلکسیشن (relaxation) مشترک در این روشها و نقش صفهای اولویت در پیادهسازی کارآمد میپردازد. کوتاهترین مسیرهای بدون وزن که با جستجوی اول سطح (breadth-first search) به دست میآیند و در بخش پیمایش گراف پوشش داده میشوند، از این بحث مستثنی هستند.
Core questions
- چگونه ریلکسیشن یال به تدریج تخمینهای فاصله را به سمت فواصل واقعی کوتاهترین مسیر دقیقتر میکند؟
- چرا الگوریتم دایکسترا برای صحیح بودن به وزنهای یال نامنفی نیاز دارد؟
- چگونه بلمن-فورد وزنهای منفی را مدیریت میکند و چرخههای منفی را تشخیص میدهد؟
- چه زمانی محاسبه کوتاهترین مسیرهای همه جفتها کارآمدتر از تکرار یک روش تک منبع است؟
- انتخابهای صف اولویت چگونه بر زمان اجرای الگوریتم دایکسترا تأثیر میگذارند؟
Key concepts
- ریلکسیشن یال
- کوتاهترین مسیرهای تک منبع
- الگوریتم دایکسترا
- الگوریتم بلمن-فورد
- چرخههای با وزن منفی
- کوتاهترین مسیرهای همه جفتها
- الگوریتم فلوید-وارشال
- پیادهسازی صف اولویت
Key theories
- ریلکسیشن یال و انتخاب حریصانه
- الگوریتمهای کوتاهترین مسیر به طور مکرر یالها را ریلکس میکنند و تخمین فاصله را زمانی که مسیر کوتاهتری یافت میشود، جایگزین میکنند؛ الگوریتم دایکسترا به طور حریصانه نزدیکترین رأس حلنشده را نهایی میکند، که دقیقاً به این دلیل صحیح است که وزن یالها نامنفی هستند.
- برنامهریزی پویا برای مسیرهای همه جفتها
- الگوریتم فلوید-وارشال کوتاهترین مسیرهای همه جفتها را با یک برنامه پویا بر روی رئوس میانی محاسبه میکند، که در زمان مکعبی اجرا میشود و به طور طبیعی وزنهای یال منفی (بدون چرخههای منفی) را مدیریت میکند.
Clinical relevance
الگوریتمهای کوتاهترین مسیر، خدمات ناوبری و نقشهبرداری، پروتکلهای مسیریابی بستهها در شبکهها، برنامهریزی مسیر در لجستیک، و هر سیستمی که مسیرهای کمهزینه را از طریق یک شبکه وزندار پیدا میکند، از جمله یافتن مسیر در بازیها و محاسبات فاصله منابع در تحلیل فضایی را پشتیبانی میکنند.
History
دایکسترا الگوریتم کوتاهترین مسیر تک منبع خود را در سال ۱۹۵۹ منتشر کرد. الگوریتم بلمن-فورد، که وزنهای منفی را مدیریت میکند، از کارهای بلمن، فورد و مور در اواخر دهه ۱۹۵۰ پدید آمد. الگوریتم فلوید در سال ۱۹۶۲، که بر اساس روش بستار ترایایی (transitive-closure) وارشال ساخته شده بود، یک راهحل فشرده برای همه جفتها ارائه داد که همچنان یک استاندارد است.
Key figures
- Edsger W. Dijkstra
- Richard Bellman
- Lester Ford
- Robert W. Floyd
Related topics
Seminal works
- dijkstra1959
- floyd1962
- cormen2009
Frequently asked questions
- چرا الگوریتم دایکسترا نمیتواند وزنهای یال منفی را مدیریت کند؟
- الگوریتم دایکسترا نزدیکترین رأس حلنشده را نهایی میکند و هرگز به آن بازنمیگردد، با فرض اینکه هیچ مسیر بعدی نمیتواند کوتاهتر باشد. یک یال منفی میتواند چنین مسیر کوتاهتری را پس از نهایی شدن یک رأس ایجاد کند و این فرض را نقض کند. در عوض، از بلمن-فورد استفاده میشود که همه یالها را به طور مکرر ریلکس میکند.
- چه زمانی باید از یک الگوریتم همه جفتها به جای اجرای دایکسترا از هر رأس استفاده کنم؟
- برای گرافهای چگال یا زمانی که به بسیاری یا همه فواصل مبدأ-مقصد نیاز است، محاسبه ساده مکعبی زمان فلوید-وارشال برای همه جفتها اغلب ارجح است. برای گرافهای خلوت، اجرای دایکسترا (یا الگوریتم جانسون برای وزنهای منفی) از هر منبع میتواند به طور مجانبی سریعتر باشد.