الگوریتم یافتن کوتاه‌ترین مسیر سریع‌تر

الگوریتم یافتن کوتاهترین مسیر سریع تر (SPFA) را می‌توان روشی برای بهبود الگوریتم بلمن-فورد معرفی کرد که با استفاده از آن کوتاهترین مسیر تک منبع در یک گراف وزندار و جهت‌دار بدست می‌آید. تحقیقات قبلی بر این باورند که این الگوریتم به خوبی روی گراف خلوت تصادفی کار می‌کند یا به صورت دقیقتر، برای گراف‌هایی که یال‌های وزن-منفی دارند پرکاربرد است.[1] با این حال، بدترین حالت پیچیدگی در SPFA همانند الگوریتم بلمن-فورد دارای نقص است که برای جبران الگوریتم Dijkstra برای گراف‌های با وزن لبه‌های غیر منفی ترجیح داده می‌شود.[2] الگوریتم SPFA برای اولین بار توسط ادوارد اف مور در سال ۱۹۵۹ معرفی شد و به چاپ رسید که خود باعث کلیت بخشیدن به الگوریتم جستجوی اول سطح شد.[3] مشابه همان الگوریتم در سال ۱۹۹۴ توسط فندینگ دوان کشف شد.[4]

الگوریتم

در حالت کلی و در یک گراف وزن دار و جهت دار ${\displaystyle G=(V,E)}$ با رأس ${\displaystyle s}$ به عنوان منبع، الگوریتم SPFA کوتاه‌ترین مسیر را از رأس ${\displaystyle s}$به هر رأس دیگر موجود در گراف ${\displaystyle v}$پیدا می‌کند. برای هر رأس گراف طول کوتاه‌ترین مسیر از ${\displaystyle s}$ به ${\displaystyle v}$در ${\displaystyle d(v)}$ذخیره می‌شود. ایده اصلی SPFA در واقع همانند الگوریتم بلمن-فورد است که به عنوان یک راه حل برای حداقل کردن فاصله هر رأس از منبع استفاده می‌شود.[5] بهبودی که SPFA نسبت به سایر روش‌ها ارائه می‌دهد باعث شده‌است که به جای امتحان کردن تصادفی تمام رأس‌ها، در SPFA تمامی رأس‌های با حداقل فاصله نسبت به منبع با روشی منظم و سریع یافته شوند.

در زیر شبه کد از الگوریتم SPFA نشان داده شده‌است.[6] ادر این الگوریتم ${\displaystyle Q}$ سری اول رأس‌های داوطلب ورودی، و ${\displaystyle w(u,v)}$وزن یال ${\displaystyle (u,v)}$است.

مثال تصویری از SPFA برای درک عمیق‌تر بر اساس فاصله اقلیدسی که در آن خطوط قرمز کوتاه‌ترین مسیر را مشخص می‌کند. خطوط آبی نشان می‌دهد که در آن شرط کوتاه‌ترین مسیر صادق است: یعنی اتصال ${\displaystyle v}$به ${\displaystyle u}$ با یک گره مسیری کوتاه‌تر از فاصله بین ${\displaystyle v}$ تا منبع را فراهم می‌کند .

 procedure Shortest-Path-Faster-Algorithm(G, s)
 1 for each vertex v ≠ s in V(G)
 2 d(v) := ∞
 3 d(s) := ۰
 4 offer s into Q
 5 while Q is not empty
 6 u := poll Q
 7 for each edge (u, v) in E(G)
 8 if d(u) + w(u, v) < d(v) then
 9 d(v) := d(u) + w(u, v)
 10 if v is not in Q then
 11 offer v into Q

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

مدت اجرا

در بدترین حالت یا غیربهینه‌ترین زمان اجرا، الگوریتم عملکردی مشابه الگوریتم استاندارد بلمن-فورد ارائه می‌دهد.[1]

روش‌های بهینه‌سازی

عملکرد الگوریتم به شدت وابسته به ترتیبی است که رأس‌های داوطلب ورودی توسط نظم تعیین می‌شود که در آن رأی‌های داوطلب برای استراحت دیگر رأس‌ها استفاده می‌شود. در واقع، اگر ${\displaystyle Q}$یک صف اولویت دار باشد، سپس الگوریتم بسیار مشابه Dijkstra است. با این حال، از آنجا که صف اولویت دار در اینجا استفاده نمی‌شود، دو روش دیگر را می‌توان برای بهبود کیفیت صف بکار برد که به نوبه خود عملکرد را در حالت کلی بهبود می‌دهد (اما نه عملکرد بدترین حالت عملکرد را). هر دو روش نظم و ترتیب المان‌های حاضر در ${\displaystyle Q}$ به نحوی تغییر می‌دهد که رأس‌های نزدیک به منبع ابتدا پردازش می‌شوند؛ بنابراین، هنگام اجرای این تکنیک‌ها ${\displaystyle Q}$ با یک لیست نرمال دو طرفه یا یک صف دوطرفه است و سیاست FIFO (خروج به ترتیب ورود) در مورد آن صادق نیست.

اولین برچسب کوچک ( SLF) (اولین بار توسط Dimitri Bertsekas مطرح شد، Vol 23، ۱۹۹۳، pp. 703-709).[7] تغییری که این روش در الگوریتم ایجاد می‌کند را می‌توان با تغییر در خط ۱۱ بیان کرد. در خط ۱۱، به جای تلاش و تأکید بر انتقال همیشگی راس ${\displaystyle v}$ به پایان صف، از شبه کد ریز برای این تکنیک استفاده می‌شود (پس از انتقال راس ${\displaystyle v}$ به پایان صف در خط ۱۱):

 procedure Small-Label-First(G, Q)
 if d(back(Q)) < d(front(Q)) then
 u := pop back of Q
 push u into front of Q

تکنیک بزرگ برچسب (LLL) (اولین بار توسط Bertsekas, Guerriero و Musmanno مطرح شد).[8] در این روش، بعد از خط ۱۱ صف به روزرسانی شده به طوری که عنصر اول کوچکتر از میانگین بوده و هر عنصر بزرگتر از میانگین به انتهای صف منتقل می‌شود. شبه کد زیر توصیف مناسبی از این تکنیک ارائه می‌دهد:

 procedure Large-Label-Last(G, Q)
 x := average of d(v) for all v in Q
 while d(front(Q)) > x
 u := pop front of Q
 push u to back of Q

منابع

1. درباره الگوریتم به اصطلاح SPFA
2. «SPFA 算法». بایگانی‌شده از اصلی در ۲ ژوئیه ۲۰۱۲. دریافت‌شده در ۲۵ آوریل ۲۰۱۹.
3. Edward F. Moore (Publisher Bell Telephone System. , 1959). «The Shortest Path Through a Maze Volume 3523 of Bell Telephone System. Technical publications. monograph». کاراکتر line feed character در |عنوان= در موقعیت 33 (کمک); تاریخ وارد شده در |تاریخ= را بررسی کنید (کمک)
4. Duan, Fanding (1994), "关于最短路径的SPFA快速算法", 西南交通大学学报 [Journal of Southwest Jiaotong University], 29 (2): 207–212
5. «Computer Science Department at Princeton University» (PDF). www.cs.princeton.edu. دریافت‌شده در ۲۰۱۹-۰۴-۱۳.
6. http://codeforces.com/blog/entry/16221
7. Chisman, James A. "Review of:"Linear Network Optimization", Dimitri P. Bertsekas, MIT Press, Cambridge, MA, Year: 1991". IIE Transactions. 24 (4): 112–112. doi:10.1080/07408179208964239. ISSN 0740-817X.
8. Bertsekas, D. P.; Guerriero, F.; Musmanno, R. "1996-02,Parallel asynchronous label-correcting methods for shortest paths". Journal of Optimization Theory and Applications. 88 (2): 297–320. doi:10.1007/bf02192173. ISSN 0022-3239.