موضوع مقاله: مسیریابی (الگوریتم) | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # مسیریابی (الگوریتم) | مقدمه: مسیر یابی یک الگوریتم برای برنامه‌های کامپیوتری است که هدف آن یافتن (غالبا) کوتاه‌ترین مسیر بین دو نقطه است. | ## بخش 1: مسیریابی (الگوریتم) | مسیر یابی به مقدار زیادی به مسئلهٔ کوتاه‌ترین مسیر در نظریهٔ گراف‌ها ارتباط دارد؛ که در واقع این مسئله به این موضوع می‌پردازد که چگونه سریع‌ترین، ارزان‌ترین (از لحاظ تعداد راس‌ها) و کوتاه‌ترین مسیر را بین دو نقطه در یک شبکهٔ بزرگ بیابیم. می‌توان تصور کرد که حتی در جوامع بسیار بدوی (حتی حیوانات) نیز این کار بسیار ضروری بوده‌است (به عنوان مثال برای یافتن غذا). از اولین الگوریتم‌هایی که برای این مسئله ارائه شد می‌توان به الگوریتم جستجوی اول سطح اشاره کرد. با توجه به پیشرفت کامپیوترها و ظهور مسائل جدید، این مسئله به تدریج از اواسط قرن بیستم مورد توجه قرار گرفت و با ایجاد شبکهٔ جهانی اینترنت، بیش از پیش به آن پرداخته شد. بازی‌های کامپیوتری و نقشه‌های آنلاین، امروزه از پیشرفته‌ترین الگوریتم‌های مسیریابی استفاده می‌کنند. تعریف مسئله مسیریابی عبارت است از پیدا کردن یک مسیر بین دو نقطه از فضا که ممکن است مابین آنها موانعی وجود داشته باشد. مسئلهٔ مسیریابی به دو زیرمسالهٔ زیر قابل تقسیم است: ایجاد یک گراف یافتن مسیر مطلوب روی گراف با طراحی یک الگوریتم مسیریابی در مرحلهٔ اول سعی بر این است که فضای پیوسته به فضایی گسسته نگاشته شود. به این ترتیب یک گراف به وجود می‌آید که در آن (مجموعهٔ رئوس گراف) نمایندهٔ نقاطی از فضای پیوسته و (مجموعهٔ یالهای گراف) نمایندهٔ وجود یا عدم وجود ارتباط بدون واسطه بین دو نقطه از فضای پیوسته‌است. خروجی این الگوریتم یک آرایه‌ی مرتب از راس‌ها است که برای رسیدن به راس هدف باید آن‌ها را به ترتیب و بدون واسطه طی کرد. الگوریتم‌های مسیریابی معمولاً علاوه بر این که می‌خواهند یک مسیر پیدا کنند، در پی مسیری هستند که بر اساس معیار خاصی (مثلا طول مسیر) بهینه باشد. الگوریتم متد مسیریابی با شروع از یک راس و جستجو در راس‌های مجاور آن تا زمان رسیدن به راس مقصد، یک گراف را جستجو می‌کند؛ که معمولاً هدف آن یافتن سریع‌ترین مسیر است. در حقیقت هدف الگوریتم مسیر یابی عموماً یافتن مسیری با کمترین تعداد راس استفاده شده (در گراف‌های فاقد وزن)، یا کمترین جمع اوزان مشاهده شده (در گراف‌های وزن‌دار) است. به عنوان مثال می‌توان گفت که الگوریتم مد نظر، همانند شخصی است که قصد دارد از نقطه‌ای به نقطهٔ دیگری برسد؛ به جای این که این شخص تمام مسیرهای موجود را بررسی کند، در یک مسیر حرکت می‌کند و فقط زمانی از مسیر خود منحرف می‌شود که مانعی بر سر راه وی وجود داشته باشد. دو نکته مهم در مسیر یابی که باید به آن توجه شود عبارت‌اند از: یافتن مسیر بین دو راس در یک گراف یافتن کوتاه‌ترین مسیر با کمترین هزینه در یک گراف الگوریتم‌های پایه ای مانند جستجوی اول سطح و جستجوی اول عمق مشکل اول را با بررسی تمام حالت‌های موجود بررسی می‌کنند. به این صورت که با گرفتن یک راس تمام مسیرهای موجود را جستجو می‌کنند تا به راس هدف برسند. از لحاظ مرتبه زمانی چنین الگوریتمی در زمان طول می‌کشد که تعداد راس‌ها و تعداد یال‌ها است. راه‌حل کلی در این موارد استفاده از الگوریتم بلمن-فورد است که پیچیدگی زمانی آن می‌باشد. اگر این گره همسایه‌ای داشته باشد که تا آن لحظه بازدید نشده باشد، الگوریتم به آن همسایه می‌رود (اگر چند همسایه با این شرایط وجود داشته باشد یکی به دلخواه انتخاب می‌شود). این روند آنقدر ادامه پیدا می‌کند تا یکی از دو اتفاق زیر بیفتد: گره پایانی مشاهده شود: در این حالت الگوریتم متوقف می‌شود و مسیر یافته شده به عنوان خروجی بازگردانده می‌شود. الگوریتم به خانه‌ای برسد که همسایهٔ بازدید نشده ندارد: در این حالت الگوریتم یک قدم پس‌گرد می‌کند و یکی از گره‌هایی که در مرحلهٔ قبل بازدید نشده بود را بازدید می‌کند. الگوریتم جستجوی اول عمق با وجود سادگی، پایهٔ بسیاری از الگوریتم‌های مهم در نظریهٔ گراف است. هدف یافتن کوتاه‌ترین مسیر از گره «آ» به گره «ح» است.این روش نخستین بار در سال ۱۹۵۹ توسط ادوارد مور برای یافتن کوتاه‌ترین مسیر در یک هزارتو معرفی شد.Moore, Edward F. 285–292 با استفاده از این الگوریتم می‌توان کوتاه‌ترین مسیر بین دو راس از یک گراف غیر وزن دار را پیدا کرد. در این روش که با استفاده از داده ساختار صف پیاده‌سازی می‌شود، قسمتی از گراف به عنوان جلودار (frontier) در نظر گرفته می‌شود. این قسمت از نقطهٔ شروع آغاز به گسترش می‌نماید و بسته به کاربرد می‌تواند تا دربرگرفتن تمام گراف یا تا حدی که نقطهٔ پایان مسیر را شامل شود گسترش یابد. در صورت پیمایش تمام گراف، می‌توان مسیر بهینه را از نقطهٔ شروع تا هر نقطهٔ دلخواه دیگر را پیدا کرد. این الگوریتم از یک حلقهٔ تکرار با دو گام زیر تشکیل می‌شود و تا خالی شدن جلودار ادامه می‌یابد: یک راس از جلودار را انتخاب کن و آن را حذف کن. همسایه‌های راس حذف شده را در صورتی که در مجموع بازدید شده‌ها (visited) نباشند به جلودار اضافه کن؛ همچنین این راس‌ها را در مجموعهٔ بازدید شده‌ها قرار بده. برای ذخیرهٔ مسیر از راس شروع تا هر راس دلخواه، باید حین اضافه کردن همسایه‌ها به جلودار، در جدولی نام راسی که همسایه‌ها از آن منشأ گرفته‌اند را نوشت. به این ترتیب پس از رسیدن به راس دلخواه (پایانی) می‌توان به صورت بازگشتی مسیری به سمت راس شروع پیدا کرد. الگوریتم اصلی دایکسترا کوتاه‌ترین مسیر را بین دو گره معین پیدا می‌کرد، اما یک نوع رایج‌تر این الگوریتم یک گره منفرد را به عنوان گره "مبدأ" مشخص می‌کند و کوتاه‌ترین مسیر را از مبدأ مشخص شده تا همهٔ گره‌های دیگر در گراف پیدا می‌کند که به آن "درخت کوتاه‌ترین مسیر (Shortest path tree)" گفته می‌شود. برای یک مبدأ مشخص شده در گراف، این الگوریتم کوتاه‌ترین مسیر را بین آن گره و سایر نقاط پیدا می‌کند. همچنین از این الگوریتم می‌توان برای یافتن کوتاه‌ترین مسیر بین دو گره مشخص استفاده کرد، به این صورت که الگوریتم از گره مبدأ آغاز می‌شود و در زمانی که به گره مقصد رسید متوقف خواهد شد. این الگوریتم کوتاه‌ترین مسیر به شکل گسترده در پروتکل‌های مسیریابی در شبکه‌ها کامپیوتری، به‌طور مثال در IS-IS یا در OSPF مورد استفاده است. الگوریتم دایکسترا از برچسب‌هایی استفاده می‌کند که اعداد صحیح مثبت یا اعداد حقیقی هستند و کاملاً مرتب شده‌اند. الگوریتم دایکسترا برای ذخیره‌سازی دسترسی به اطلاعات ذخیره‌شده، از یک داده ساختار استفاده می‌کند. الگوریتم اصلی از صف اولویت‌دار استفاده می‌کند و پیچیدگی آن (جایی که تعداد گره‌ها است) می‌باشد. | ## بخش 2: مسیریابی (الگوریتم) | با استفاده از یک صف اولویت‌دار در هرم فیبوناچی پیچیدگی زمان اجرا را به (که تعداد لبه‌ها است) رساندند. این الگوریتم به صورت مجانبی سریعترین الگوریتم یافتن کوتاه‌ترین مسیر از یک مبدأ برای یک گراف جهت دار با وزنهای غیر منفی بدون محدودیت شناخته شده‌است. الگوریتم دایکسترا مقادیر اولیه‌ای (معمولا صفر برای گره اولیه و بی‌نهایت برای سایر گره‌ها) را به گره‌ها نسبت می‌دهد و در هر مرحله آن را بهبود می‌بخشد. سپس مجموعه‌ای از همهٔ گره‌های بازدید نشده می‌سازیم و آن را مجموعه «بازدیدنشده» نام‌گذاری می‌کنیم. فاصلهٔ تازه محاسبه شده را با مقدار تعیین شدهٔ فعلی مقایسه می‌کنیم و کوچک‌ترین آن‌ها را به آن گره اختصاص می‌دهیم. به عنوان مثال، اگر گره فعلی A با فاصلهٔ 6 علامت‌گذاری شود و یالی که آن را به B متصل می‌کند دارای طول 2 باشد، در این صورت فاصله تا B از A برابر 6 + 2 = 8 خواهد بود. وقتی همهٔ همسایگان گره فعلی که «دیده‌نشده» نشانه‌گذاری شده بودند را پیمایش کردیم و به آنها یک فاصله اختصاص دادیم، گره فعلی را «بازدیدشده» علامت‌گذاری می‌کنیم و آن را از مجموعه «بازدیدنشده» خارج می‌کنیم. اگر گره مقصد مورد بازدید قرار گرفته شده باشد (هنگام پیدا کردن مسیری بین دو گره خاص) یا اگر کوچک‌ترین فاصله در بین گره‌های موجود در مجموعهٔ بازدیدنشده بی‌نهایت باشد (هنگام پیدا کردن یک گذر کامل؛ وقتی اتفاق می‌افتد که هیچ ارتباطی بین آن گره‌ها و گره اولیه وجود ندارد و گره‌ها بازدیدنشده باقی می‌مانند)، دیگر الگوریتم را ادامه نمی‌دهیم. در غیر این صورت، گره بازدیدنشده را که با کم‌ترین فاصله مشخص شده‌است، انتخاب می‌کنیم، آن را به عنوان «گره فعلی» جدید تنظیم می‌کنیم و به مرحله 3 برمی‌گردیم. هنگام پیدا کردن یک مسیر، لازم نیست صبر کنیم تا گره مقصد مانند «فوق» بازدید شود: الگوریتم می‌تواند هنگامی که گره مقصد کم‌ترین فاصله را بین همهٔ گره‌های «بازدیدنشده» داشته باشد متوقف شود (و بنابراین این گره می‌تواند به عنوان گره «فعلی» بعد از گره مبدأ مورد استفاده قرار گیرد). فرض کنید می‌خواهیم کوتاه‌ترین مسیر بین دو نقطه روی نقشه را پیدا کنیم، یکی از این دو نقطه را نقطهٔ شروع و دیگری را به عنوان مقصد در نظر می‌گیریم. الگوریتم دایکسترا در ابتدا فاصلهٔ هر نقطهٔ تقاطع تا مبدأ روی نقشه را با بی‌نهایت نشانه گذاری می‌کند. این کار به این معنی نیست که فاصله‌ها بی‌نهایت هستند، بلکه به این معنا است که این نقاط تقاطع هنوز بازدید نشده‌اند (روش‌هایی نیز وجود دارند که تقاطع‌های بازدید نشده را در ابتدا نشانه گذاری نمی‌کنند). در اولین مرحله، تقاطع فعلی، نقطهٔ شروع بوده و فاصله تا آن صفر خواهد بود (پس این نقطه را با صفر نشانه‌گذاری می‌کنیم). در مراحل بعد، نقطه‌ای که روی آن قرار داریم نزدیک‌ترین نقطه به مبدأ خواهد بود (پیدا کردن آن نیز کاری آسان خواهد بود). از تقاطع فعلی، فاصلهٔ تمام نقاط تقاطعی که به آن به‌طور مستقیم متصل هستند و بازدید نشده‌اند را به‌روزرسانی می‌کنیم. این کار را به این صورت انجام می‌دهیم که مجموع فاصلهٔ نقطهٔ تقاطع مورد نظر با تقاطع فعلی را با نشانه‌ای که برای تقاطع فعلی در نظر گرفته‌ایم حساب می‌کنیم، پس از آن اگر مجموع حساب‌شده از نشانهٔ آن تقاطع بازدیدنشده کمتر بود آن را با مقدار جدید نشانه‌گذاری می‌کنیم. بعد از اینکه مسافت‌ها را برای هر تقاطع همسایه به‌روزرسانی کردیم، تقاطع فعلی را به عنوان بازدیدشده علامت‌گذاری می‌کنیم و یک تقاطع بازدید نشده با حداقل فاصله (از نقطهٔ شروع) -یا کمترین عدد نشانه‌گذاری شده روی آن- را به عنوان تقاطع فعلی انتخاب می‌کنیم. تقاطع‌هایی که به عنوان بازدیدشده هستند با کوتاه‌ترین مسیر از نقطهٔ مبدأ تا آن برچسب خورده‌اند و قابل بازنگری یا بازگشت به آن نخواهند بود. این روند یعنی به روز رسانی تقاطع‌های همسایه با کمترین فاصلهٔ آن‌ها تا مبدأ، نشانه‌گذاری تقاطعی که روی آن بودیم به عنوان بازدیدشده و سپس انتخاب نزدیک‌ترین تقاطع همسایه به عنوان تقاطع بعدی را ادامه می‌دهیم تا زمانی که نقطهٔ مقصد مورد نظر را به عنوان بازدیدشده مشخص کنیم. هنگامی که مقصد را به عنوان بازدیدشده مشخص کردیم کوتاه‌ترین مسیر از نقطهٔ مبدأ تا آن را تعیین کرده‌ایم و می‌توانیم مسیر خود را به عقب با دنبال کردن جهت معکوس پیکان‌ها ردیابی کنیم. در اجرای الگوریتم، این کار معمولاً بدین صورت انجام می‌شود که از نقطهٔ مقصد شروع به دنبال کردن والدین آن و پس از آن والدین نقطهٔ بعدی می‌کنیم تا به نقطهٔ مبدأ برسیم. این الگوریتم همان‌طور که انتظار می‌رود هیچ تلاشی برای «کاوش» مستقیم به سمت نقطهٔ مقصد انجام نمی‌دهد. در عوض، تنها نکتهٔ مورد نظر برای تعیین نقطهٔ تقاطع بعدی، فاصله آن از نقطهٔ شروع است. این نکته نیز ممکن است یکی از نقاط ضعف الگوریتم را نشان دهد، کندی نسبی آن در برخی توپولوژی‌ها. متغیر در خط 18 طول مسیر از گره ریشه (نقطهٔ مبدأ) تا گره همسایه است به طوری که این مسیر از گره عبور کند. اگر این مسیر محاسبه شده کوتاه‌تر از کوتاه‌ترین مسیری باشد که برای ثبت شده‌است، مسیر محاسبه‌شده در متغیر با مسیر قبلی جایگزین می‌شود. یک مسئلهٔ کلی تر این است که همهٔ کوتاهترین مسیرها را بین مبدأ و مقصد پیدا کنیم (ممکن است چندین مسیر مختلف با طول یکسان وجود داشته باشد). در این صورت به جای این که فقط یک گره را هر بار در آرایه ذخیره کنیم، تمام گره‌هایی که شرایط مورد نظر در الگوریتم را برآورده می‌سازد در آن ذخیره می‌کنیم. به عنوان مثال، اگر هم گره و هم مبدأ، متصل به گره مقصد باشند و هر دوی آن‌ها شامل کوتاه‌ترین مسیرهای مختلف به گره مقصد باشند، هر دو را به آرایه اضافه می‌کنیم. وقتی که الگوریتم به پایان رسید، در واقع یک ساختار داده خواهد بود که زیرمجموعه‌ای از گراف اصلی است به طوری که برخی از یال‌های آن برداشته شده‌است. ویژگی اصلی این ساختار داده این خواهد بود که اگر الگوریتم برای همهٔ گره‌ها به عنوان گره مبدأ اجرا شود، آنگاه هر مسیری از آن گره به هر گره دیگر در گراف جدید، کوتاه‌ترین مسیر بین آن گره‌ها در گراف اصلی خواهد بود، و تمام مسیرهایی از آن طول در گراف اصلی در گراف جدید نیز موجود است. سپس برای یافتن همه این کوتاه‌ترین مسیرها بین دو گره داده شده، از الگوریتمی برای یافتن مسیر در گراف جدید مانند جستجوی اول عمق استفاده خواهیم کرد. الگوریتم بلمن-فورد مقالهٔ اصلی: الگوریتم بلمن-فورد مقدمه الگوریتم Bellman-Ford الگوریتمی برای پیدا کردن کوتاه‌ترین مسیر از یک راس گراف به عنوان منبع به کلیه راس‌های دیگر در یک گراف وزن‌دار است. این الگوریتم در حل یک مسئله مشخص از الگوریتم دکسترا کندتر است، اما برای حل مسائل بیشتری کاربرد دارد، زیرا این قابلیت را دارد که برای گراف‌هایی با وزن منفی نیز استفاده شود. این الگوریتم برای اولین بار توسط آلفونسو شیمبل ارائه شده‌است، اما به نام ریچارد بلمن و لستر فورد جونیور نامگذاری شده‌است که به ترتیب در سال ۱۹۵۸ و ۱۹۵۶ این الگوریتم را منتشر کردند. مور نیز در سال ۱۹۵۷ همین الگوریتم را منتشر کرد و به همین دلیل گاهی اوقات الگوریتم بلمن-فورد-مور نیز نامیده می‌شود. | ## بخش 3: مسیریابی (الگوریتم) | یال‌های منفی گراف‌ها در بسیاری از مسائل کاربرد دارد، از این رو این الگوریتم می‌تواند از جهت کمک به حل این نوع از مسائل بسیار سودمند باشد. اگر یک گراف شامل یک «دور منفی» (یعنی دوری که مجموع وزن یال‌های آن به یک مقدار منفی برسد) که از مبدأ قابل دسترسی باشد، کوتاهترین مسیر وجود ندارد: هر مسیری که دارای یک راس در دور منفی باشد می‌تواند با هر بار پیمایش دور منفی موجود در گراف به مسیر کوتاه تری تبدیل شود. الگوریتم مانند الگوریتم دایکسترا، بلمن-فورد با استفاده از روش «ریلکس» کردن (relaxation) پیش می‌رود، که در آن تقریب فاصلهٔ صحیح با فواصل بهتر در طول الگوریتم جایگزین می‌شود تا اینکه در نهایت به بهترین جواب برسد. در هر دو الگوریتم، فاصلهٔ تقریبی مبدأ با هر راس در گراف همیشه فراتر از فاصلهٔ واقعی است و در طول اجرا با حداقل مقدار از بین مقدار قدیمی آن و مسیر تازه پیدا شده جایگزین می‌شود. با این حال، الگوریتم دایکسترا از صف اولویت دار برای انتخاب حریصانه‌ی نزدیکترین راسی که هنوز پردازش نشده‌است استفاده می‌کند و همین روند را برای تمامی یال‌های خروجی راس‌ها انجام می‌دهد. در مقابل، الگوریتم بلمن-فورد به راحتی تمام یال‌ها را «ریلکس» می‌کند و ریلکس کردن را بار انجام می‌دهد، که در آن تعداد راس‌های موجود در گراف است. در هر یک از این تکرارها تعداد راس‌ها با فاصلهٔ درست از مبدأ رشد می‌کند، که در نهایت منجر به این می‌شود که فاصله همه راس‌ها از مبدأ به‌طور صحیح محاسبه شود. این روش اجازه می‌دهد تا الگوریتم بلمن-فورد برای طیف گسترده‌تری از گراف‌ها به عنوان ورودی اجرا شود. به عبارت ساده، این الگوریتم در ابتدای کار فاصلهٔ مبدأ را برابر صفر و همه راس‌های دیگر گراف را بی‌نهایت قرار می‌دهد. سپس برای همه یال‌ها، اگر با در نظر گرفتن آن یال فاصلهٔ مقصد کاهش پیدا کند، فاصله به مقدار کمتر جدید به روز می‌شود. در ‌اُمین بار تکرار الگوریتم که یال‌ها مورد بررسی قرار می‌گیرند، این الگوریتم تمام مسیرهای با طول یال (و احتمالاً برخی از مسیرهای طولانی‌تر از یال) پیدا می‌کند. از آنجایی که طولانی‌ترین مسیر ممکن بدون دور می‌تواند شامل یال باشد، یال‌ها باید بار بررسی شوند تا مطمئن شویم که کوتاه‌ترین مسیر برای همه راس‌ها پیدا شده‌است. بررسی نهایی برای تمامی یال‌ها انجام می‌شود و اگر فاصله‌ای به روز شود، مسیری به طول یال پیدا شده‌است که تنها در صورت وجود حداقل یک دور با وزن منفی در گراف می‌تواند رخ دهد. در واقع این الگوریتم ترکیبی از الگوریتم Dijkstra و الگوریتم جستجوی ابتدا-بهترینِ حریصانه است و در عین حال که کوتاه‌ترین مسیر را می‌یابد (البته در مواردی که خانه‌های بسته -خانه‌هایی که غیرقابل عبورند- وجود دارد این ویژگی تضمین شده نیست)، از هر دو سریعتر کار می‌کند. سپس نقطه مبدأ را به لیست بسته اضافه می‌کنیم و در هر مرحله راس‌های قابل تردد همسایهٔ راس فعلی را به لیست باز اضافه می‌کنیم. حال باید دو تابع تعریف کنیم: تابع G: هزینهٔ رسیدن تا مکان فعلی (مقدار یال‌های طی شده از مبدأ تا راس فعلی) تابع H: هیوریستیک یا تخمین هزینهٔ رسیدن از راس فعلی تا مقصد حال اگر تعریف کنیم: (F(node) = G(node) + H(node، آنگاه این تابع برآورد کم‌هزینه‌ترین مسیر از node به مقصد است. برای محاسبهٔ G مقدار G والد (آخرین راس قبل از راس فعلی که از آن گذشته‌ایم) آن راس را یک واحد بیشتر می‌کنیم. اگر T در هیچ‌کدام نبود، به لیست باز اضافه شده و مقدار توابع G و H و Fاش محاسبه می‌شود. در نقشهٔ زیر x نماد مکان‌های بسته یا دیوار، s محل شروع، o نقطهٔ پایان و _ مکان‌های باز نقشه را نشان می‌دهند. سپس بر روی تمام اعضای صف پیمایش انجام می‌شود و اعمال زیر برای هر عضو انجام می‌شود. یک لیست از چهار عنصر مجاور آن تشکیل داده می‌شود که یرای هر عنصر متغیر شمارندهٔ آن، شمارندهٔ عنصر در صف به علاوهٔ یک می‌باشد؛ که در مثال بالا این لیست به صورت ۲٬۸٬۱),(۳٬۷٬۱),(۴٬۸٬۱),(۳٬۹٬۱ است. حال عناصر موجود در این لیست جدید بررسی می‌شود که اگر آن عنصر ذیوار بود یا در لیست اصلی مختصاتی مشابه با شمارندهٔ کمتر وجود داشت حذف می‌شود. هنگامی که به نقطه شروع برسیم مشاهده می‌شود که نقاطی که در صف هستند، یک مقدار شمارنده به آنها تخصیص داده شده‌است. مقایسهٔ الگوریتم‌ها در جدول زیر، الگوریتم‌های شاخص مسیریابی از جهت پیچیدگی زمانی و مورد کاربرد با یکدیگر مقایسه شده‌اند. +الگوریتمپیچیدگی زمانیتوضیحاتجستجوی اول عمقبرای گراف‌های بدون وزنجستجوی اول سطحبرای گراف‌های بدون وزندایکسترابرای گراف‌های وزن‌دار بدون دور منفیبلمن-فوردبرای گراف‌های وزن‌دار با قابلیت اعمال بر گراف‌های دارای دور منفی*Aبرای گراف‌های وزن‌دار بدون دور منفی کاربردهای مسیریابی مسیریابی در شبکه‌های کامپیوتری: برای انتقال داده بین دو گره شبکه از الگوریتم‌های مسیریابی برای پیدا کردن بهترین مسیر بین دو گره استفاده می‌شود. بازی‌های کامپیوتری: الگوریتم‌های مسیریابی در واقع هستهٔ هر سیستم حرکتی مجهز به هوش مصنوعی هستند. الگوریتم‌های مسیریابی در بازی‌های کامپیوتری وظیفه دارند تا بین هر دو نقطهٔ روی مختصات بازی بهترین مسیر را پیدا کنند. نقشه‌های آنلاین: استفادهٔ این برنامه‌ها از مسیریابی در زندگی روزمره بسیار زیاد است. الگوریتم‌های مسیریابی باید بتوانند در هر زمانی با در نظر گرفتن متغیرهای مختلفی (اعم از ترافیک، مسیرهای مسدودشده و …) مسیرهای مناسب را به کاربران پیشنهاد دهند. این امر به این شکل انجام می‌گیرد که مسیرهای تصادفی بین مکان‌هایی که مردم علاقه زیادی به استفاده از آنها دارند انتخاب می‌شود. سپس با توجه به اینکه کدام مسیرها فضای بیشتری را روی نقشه پوشش می‌دهند، جاده‌ها روی آن‌ها بنا می‌شوند. از این الگوریتم برای ساختن انواع راه‌ها مانند بزرگراه‌ها، جاده‌های بین شهری، راه‌های خاکی و … استفاده می‌شود. یکی از مهم‌ترین کاربردهای این الگوریتم در ساختن جاده‌های کوهستانی است که برای پرهیز از شیب‌های تند استفاده می‌شود. شهرسازی: مناطقی که محل تقاطع چند مسیر مختلف هستند محل مناسبی برای ساختن شهرها محسوب می‌شوند. تجزیه و تحلیل زمین: با استفاده از همان رویکرد راه‌سازی، می‌توان از مسیریابی استفاده کرد تا مشخص شود که چه مناطقی احتمالاً بیشتر در مسیر رفت و آمد قرار دارند. مکان یابی در محیط‌های رزمی: از همان روش بالا برای تجزیه و تحلیل زمین، با تجزیه و تحلیل بیشتر مسیر، می‌توانیم مکان‌هایی را در طول مسیر پیدا کنیم که برای دشمن تا N قدم بعدی در مسیر متنهی به آن قابل رویت نباشد. قرار دادن کمین در یکی از این نقاط بدان معنی است که دشمن تا زمانی که در فاصله N قرار نگیرید، شما را نمی‌بیند، بنابراین می‌توان با یک نیروی بزرگ کمین کرد. | ## جمع‌بندی | رباتیک: از جمله مسائل مهم در ربات‌های متحرک مسیریابی می‌باشد که هوش مصنوعی به آن ورود کرده‌است.