الگوریتم یافتن کوتاه‌ترین مسیر سریع‌تر کیست؟ توضیح بده.
الگوریتم یافتن کوتاهترین مسیر سریع تر (SPFA) را می‌توان روشی برای بهبود الگوریتم بلمن-فورد معرفی کرد که با استفاده از آن کوتاهترین مسیر تک منبع در یک گراف وزندار و جهت‌دار بدست می‌آید. تحقیقات قبلی بر این باورند که این الگوریتم به خوبی روی گراف خلوت تصادفی کار می‌کند یا به صورت دقیقتر، برای گراف‌هایی که یال‌های وزن-منفی دارند پرکاربرد است. با این حال، بدترین حالت پیچیدگی در SPFA همانند الگوریتم بلمن-فورد دارای نقص است که برای جبران الگوریتم Dijkstra برای گراف‌های با وزن لبه‌های غیر منفی ترجیح داده می‌شود. الگوریتم SPFA برای اولین بار توسط ادوارد اف مور در سال ۱۹۵۹ معرفی شد و به چاپ رسید که خود باعث کلیت بخشیدن به الگوریتم جستجوی اول سطح شد. مشابه همان الگوریتم در سال ۱۹۹۴ توسط فندینگ دوان کشف شد.الگوریتم.در حالت کلی و در یک گراف وزن دار و جهت دار formula_1 با رأس formula_2 به عنوان منبع، الگوریتم SPFA کوتاه‌ترین مسیر را از رأس formula_2به هر رأس دیگر موجود در گراف formula_4پیدا می‌کند. برای هر رأس گراف طول کوتاه‌ترین مسیر از formula_2 به formula_4در formula_7ذخیره می‌شود. ایده اصلی SPFA در واقع همانند الگوریتم بلمن-فورد است که به عنوان یک راه حل برای حداقل کردن فاصله هر رأس از منبع استفاده می‌شود. بهبودی که SPFA نسبت به سایر روش‌ها ارائه می‌دهد باعث شده‌است که به جای امتحان کردن تصادفی تمام رأس‌ها، در SPFA تمامی رأس‌های با حداقل فاصله نسبت به منبع با روشی منظم و سریع یافته شوند.در زیر شبه کد از الگوریتم SPFA نشان داده شده‌است. ادر این الگوریتم formula_8 سری اول رأس‌های داوطلب ورودی، و formula_9وزن یال formula_10است. procedure Shortest-Path-Faster-Algorithm("G", "s") 1 for each vertex "v" ≠ "s" in "V"("G") 2 d("v") := ∞ 3 d("s") := 0 4 push "s" into "Q" 5 while "Q" is not empty do 6 "u" := poll "Q" 7 for each edge ("u", "v") in "E"("G") do 8 if d("u") + w("u", "v") &lt; d("v") then 9 d("v") := d("u") + w("u", "v") 10 if "v" is not in "Q" then 11 push "v" into "Q"الگوریتم همچنین می‌تواند برای یک گراف بدون جهت به کار گرفته شود که در این حالت هر یک از یال‌های بدون جهت با دو یال جهت‌دار با جهت‌های معکوس جایگزین می‌شود.مدت اجرا.در بدترین حالت یا غیربهینه‌ترین زمان اجرا، الگوریتم عملکردی مشابه الگوریتم استاندارد بلمن-فورد ارائه می‌دهد.روش‌های بهینه‌سازی.عملکرد الگوریتم به شدت وابسته به ترتیبی است که رأس‌های داوطلب ورودی توسط نظم تعیین می‌شود که در آن رأی‌های داوطلب برای استراحت دیگر رأس‌ها استفاده می‌شود. در واقع، اگر formula_8یک صف اولویت دار باشد، سپس الگوریتم بسیار مشابه Dijkstra است. با این حال، از آنجا که صف اولویت دار در اینجا استفاده نمی‌شود، دو روش دیگر را می‌توان برای بهبود کیفیت صف بکار برد که به نوبه خود عملکرد را در حالت کلی بهبود می‌دهد (اما نه عملکرد بدترین حالت عملکرد را). هر دو روش نظم و ترتیب المان‌های حاضر در formula_8 به نحوی تغییر می‌دهد که رأس‌های نزدیک به منبع ابتدا پردازش می‌شوند؛ بنابراین، هنگام اجرای این تکنیک‌ها formula_8 با یک لیست نرمال دو طرفه یا یک صف دوطرفه است و سیاست FIFO (خروج به ترتیب ورود) در مورد آن صادق نیست.اولین برچسب کوچک ( SLF) (اولین بار توسط مطرح شد، Vol 23، ۱۹۹۳، pp. 703-709). تغییری که این روش در الگوریتم ایجاد می‌کند را می‌توان با تغییر در خط ۱۱ بیان کرد. در خط ۱۱، به جای تلاش و تأکید بر انتقال همیشگی راس formula_4 به پایان صف، از شبه کد ریز برای این تکنیک استفاده می‌شود (پس از انتقال راس formula_4 به پایان صف در خط ۱۱): procedure Small-Label-First(G, Q) if d(back(Q)) &lt; d(front(Q)) then u := pop back of Q push u into front of Qتکنیک بزرگ برچسب (LLL) (اولین بار توسط , Guerriero و Musmanno مطرح شد). در این روش، بعد از خط ۱۱ صف به روزرسانی شده به طوری که عنصر اول کوچکتر از میانگین بوده و هر عنصر بزرگتر از میانگین به انتهای صف منتقل می‌شود. شبه کد زیر توصیف مناسبی از این تکنیک ارائه می‌دهد: procedure Large-Label-Last(G, Q) x := average of d(v) for all v in Q while d(front(Q)) &gt; x u := pop front of Q push u to back of Q