مسئله یافتن کوتاه‌ترین مسیر در گراف – بررسی الگوریتم‌های دایجسترا، بلمن-فورد و فلوید

مسئله یافتن کوتاه‌ترین مسیر در یک گراف (Shortest path problem)، یکی از مسائل اساسی و پرکاربرد در علوم رایانه و ریاضیات است. این مسئله در بسیاری از زمینه‌ها از جمله شبکه‌های کامپیوتری، حمل‌ونقل، طراحی مدارهای الکتریکی و حتی در بازی‌های ویدئویی کاربرد دارد. در این مقاله، با انواع این مسئله و الگوریتم‌های مختلفی که برای حل این مسئله استفاده می‌شوند، آشنا می‌شویم.

گراف چیست؟

گراف (Graph) یک ساختار ریاضی است که برای مدل‌سازی روابط بین اشیاء استفاده می‌شود. این ساختار از مجموعه‌ای از نقاط به نام راس (Nodes) یا راس (Vertices) و مجموعه‌ای از خطوط به نام یال یا یال (Edges) تشکیل شده است که این نقاط را به یکدیگر متصل می‌کند. راس‌ها نقاطی هستند که موجودیت‌های مختلف را در گراف نمایندگی می‌کنند. مثلاً در یک شبکه اجتماعی، راس‌ها می‌توانند نمایانگر افراد باشند. یال‌ها خطوطی هستند که راس‌ها را به یکدیگر متصل می‌کنند و نشان‌دهنده روابط یا ارتباطات بین آن‌ها هستند. مثلاً در همان شبکه اجتماعی، یال‌ها می‌توانند نشان‌دهنده دوستی بین افراد باشند.

انواع گراف

گراف‌ها می‌توانند بسته به نوع و ویژگی‌هایشان به چندین دسته تقسیم شوند، اصلی‌ترین این دسته‌بندی‌ها به شرح زیر است:

• گراف‌های جهت‌دار (Directed Graphs): در این نوع گراف‌ها، هر یال دارای یک جهت مشخص است که نشان می‌دهد ارتباط از کدام راس به کدام راس دیگر برقرار می‌شود.
• گراف‌های بدون جهت (Undirected Graphs): در این نوع گراف‌ها، یال‌ها جهت ندارند و ارتباط بین راس‌ها دو طرفه است.
• گراف‌های وزن‌دار (Weighted Graphs): در این نوع گراف‌ها، هر یال دارای یک وزن مشخص است که معمولاً نشان‌دهنده هزینه، فاصله یا هر معیار دیگری از ارتباط بین دو راس است.
• گراف‌های بدون وزن (Unweighted Graphs): در این نوع گراف‌ها، یال‌ها وزن ندارند و تنها وجود یا عدم وجود ارتباط بین راس‌ها مهم است.

برای مطالعه بیشتر در مورد گراف و انواع آن مقاله نظریه گراف: پلی بین ریاضیات و دنیای واقعی را بخوانید.

همان‌طور که متوجه شدید گراف‌ها انواع مختلفی دارند، در نتیجه نمی‌توان انتظار داشت یک الگوریتم واحد بتواند تمامی مسائل مربوط به کوتاه‌ترین مسیر را حل کند. پیش از بررسی الگوریتم‌های این مسئله، لازم است دو دسته کلی مسائل کوتاه‌ترین مسیر را معرفی کنیم:

مسئله کوتاه‌ترین مسیر در گراف با یک مبدا

در الگوریتم‌های حل مسئله کوتاه‌ترین مسیر با یک مبدا (Single Source Shortest Path)، هدف یافتن کوتاه‌ترین مسیر از یک راس مبدا به تمام راس‌های دیگر گراف است. به عبارت دیگر، در این الگوریتم‌ها تنها یک راس مبدا داریم و کوتاه‌ترین مسیر از این راس به تمامی راس‌های دیگر گراف محاسبه می‌شود.

این الگوریتم‌ها برای حل مسائل مختلفی مانند مسیریابی در شبکه‌های کامپیوتری، نقشه‌های شهری و بهینه‌سازی مسیرها در سیستم‌های حمل‌ونقل استفاده می‌شوند.

مسئله کوتاه‌ترین مسیر در گراف برای همه جفت‌ راس‌ها

برخلاف الگوریتم‌های کوتاه‌ترین مسیر با یک مبدا که تنها کوتاه‌ترین مسیر از یک راس مبدا به تمام راس‌های دیگر را محاسبه می‌کنند، الگوریتم‌های حل مسئله کوتاه‌ترین مسیر برای همه جفت راس‌ها (All Pairs Shortest Path) به دنبال تعیین کوتاه‌ترین مسیر بین هر جفت ممکن از راس‌ها در یک گراف هستند.

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

در ادامه الگوریتم‌های مناسب حل هر دسته از این مسائل را بررسی می‌کنیم:

یافتن کوتاه‌ترین مسیرهای هم‌مبدا در گراف

همان‌طور که اشاره شد، یافتن کوتاه‌ترین مسیرهای هم‌مبدا در گراف‌ها، الگوریتم‌های مختص به خود را دارد. اما این مسئله را نیز می‌توان براساس نوع گراف به دو زیر مسئله دیگر تبدیل کرد:

یافتن کوتاه‌ترین مسیرهای هم‌مبدا در گراف وزن‌دار

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

الگوریتم دایجسترا

الگوریتم دایجسترا (Dijkstra’s Algorithm) یک الگوریتم حریصانه (Greedy algorithm) برای یافتن کوتاه‌ترین مسیر در گراف وزن‌دار از یک راس مبدا به تمامی راس‌های دیگر است. این الگوریتم از یک راس مبدا شروع می‌شود و به تدریج فاصله کوتاه‌ترین مسیرها به سایر راس‌ها را محاسبه می‌کند. توجه کنید که الگوریتم دایجسترا برای گراف‌هایی که یال منفی داشته باشند درست کار نمی‌کند.

تاریخچه الگوریتم دایجسترا

الگوریتم دایجسترا توسط یک دانشمند کامپیوتر هلندی به نام ادسخر دایجسترا (Edsger Dijkstra) در سال ۱۹۵۶ ابداع شد و اولین بار در سال ۱۹۵۹ منتشر شد. دایجسترا این الگوریتم را برای یافتن کوتاه‌ترین مسیر در شبکه‌های حمل و نقل توسعه داد، اما به سرعت مشخص شد که این الگوریتم در حل مسائل گراف نیز کاربرد دارد. الگوریتم دایجسترا به دلیل سادگی و کارایی‌اش به یکی از مهم‌ترین الگوریتم‌ها در نظریه گراف تبدیل شد.

الگوریتم دایجسترا چطور کار می‌کند؟

برای اجرای این الگوریتم مراحل زیر را به ترتیب انجام می‌دهیم:

• ابتدا فاصله راس مبدا تا خودش را به صفر و تا سایر راس‌ها را به بی‌نهایت (∞) مقداردهی می‌کنیم.
• سپس یک مجموعه خالی برای ذخیره راس‌های بازدیدشده (راس‌هایی که کوتاه‌ترین مسیر رسیدن به آن‌ها محاسبه شده)، ایجاد می‌کنیم.
• در مرحله بعدی راس‌ای که کمترین فاصله را از راس مبدا دارد و هنوز بازدید نشده، انتخاب می‌کنیم.
• راس انتخاب‌شده را به مجموعه راس‌های بازدیدشده اضافه می‌کنیم.
• فاصله راس انتخاب‌شده تا راس‌های همسایه را محاسبه و در صورت کوتاه‌تر بودن به‌روزرسانی می‌کنیم.
• مراحل ۳ تا ۵ را تا زمانی که همه راس‌ها بازدید شوند، تکرار می‌کنیم.

خروجی الگوریتم دایجسترا چیست؟

با کمی دقت می‌توان فهمید که نتیجه حاصل از اجرای الگوریتم دایجسترا روی یک گراف وزن‌دار (بدون وزن منفی) یک درخت خواهد بود که کوتاه‌ترین مسیر در گراف را بین راس مبدا و راس‌های دیگر نشان می‌دهد. به این درخت، درخت کوتاه‌ترین مسیر (Shortest Path Tree – SPT) می‌گوییم.

بررسی گام‌به‌گام مراحل اجرای الگوریتم دایجسترا

برای بررسی گام‌به‌گام این الگوریتم، فرض کنید می‌خواهیم درخت کوتاه‌ترین مسیر گراف زیر را بدست آوریم:

مقداردهی اولیه

برای محاسبه درخت کوتاه‌ترین مسیر این گراف، راس A را به عنوان راس مبدا انتخاب می‌کنیم. برای اینکه مراحل اجرای این الگوریتم را راحت‌تر دنبال کنیم، یک جدول به صورت زیر در نظر می‌گیریم. در ستون اول این جدول راس‌ها بازدیدشده (Visited) را نگه می‌داریم. همان‌طور که در بخش قبل توضیح دادیم، وقتی می‌گوییم راسی بازدید شده که کوتاه‌ترین مسیر آن از راس A بدست آمده باشد.

ستون دوم این جدول، فاصله (Distance) کوتاه‌ترین مسیر از یک راس تا راس A را نگه می‌دارد. این مقدار را ابتدا به بی‌نهایت تنظیم می‌کنیم. مقادیر این ستون به طور موقتی پر می‌شوند و ممکن است با پیشرفت الگوریتم تغییر کنند. وقتی راسی بازدید شده باشد، فاصله واقعی کوتاه‌ترین مسیر آن مشخص خواهد شد. ستون آخر این جدول راس قبلی (Previous) در کوتاه‌ترین مسیر را ذخیره می‌کند.

در اجرای الگوریتم دایجسترا روی این گراف، راس‌ها بازدیدشده را با رنگ قرمز، راس‌های که همچنان فاصله رسیدن به آن‌ها بی‌نهایت است با رنگ خاکستری و سایر راس‌ها – که با فاصله‌ای کمتر از بی‌نهایت به آن‌ها رسیده‌ایم اما هنوز کوتاه‌ترین مسیر رسیدن به آن‌ها را بدست نیاورده‌ایم – را با رنگ آبی نشان می‌دهیم.

همان‌طور که انتظار داریم ابتدا فاصله همه راس‌ها بی‌نهایت تنظیم شده و هیچ کدام بازدید نشده‌اند:

بازدید راس A

در این مرحله، فاصله راس A را به صفر تغییر داده و چون مسیر دیگری برای رسیدن به آن نداریم، به عنوان راس بازدیدشده در جدول ثبت می‌کنیم. سپس باید فاصله مسیر رسیدن به همسایه‌های بازدیدنشده A (راس‌ها B و E) را محاسبه و در صورت کمتر بودن این فاصله از فاصله فعلی‌شان آن را به‌روزرسانی نماییم. برای مثال در مورد راس B، این فاصله از مجموع مسیر رسیدن به راس A (صفر) و وزن یال AB (هفت) بدست می‌آید. چون حاصل (۷) کمتر از فاصله فعلی رسیدن به راس  B(بی‌نهایت) است، فاصله موقت راس A به B را برابر با ۷ تنظیم کرده و A را به عنوان راس قبل از آن مشخص می‌کنیم. به همین ترتیب، فاصله موقت راس A به E را برابر با ۱ و A را به عنوان راس قبلی آن مشخص می‌کنیم:

بازدید راس E

در مرحله بعد باید از بین راس‌ها بازدیدنشده، راسی را که فاصله موقت رسیدن به آن از سایر راس‌ها کمتر است، انتخاب کرده و آن را به عنوان راس بازدیدشده علامت بزنیم. با توجه به جدول بالا راس E این ویژگی را دارد چون به جز راس A که بازدید شده، نسبت به سایر راس‌ها با فاصله کمتری قابل دسترسی است (فاصله راس B، ۷ و بقیه بی‌نهایت هستند). به این ترتیب راس E را ملاقات کرده و این یعنی اکنون می‌دانیم که کوتاه‌ترین فاصله از A به E برابر با ۱ است.

چرا راس E را انتخاب کردیم؟

همان‌طور که توضیح دادیم، ما E را به این علت انتخاب کردیم که کوچک‌ترین فاصله موقت را داشت. مسیر رسیدن از A به E می‌تواند مستقیم باشد، یا می‌تواند از B بگذرد. مثلاً می‌توانیم به جای AE، مسیر ABE یا حتی ABCE را طی کنیم. اما نکته این است که فاصله A به B بیشتر از فاصله A به E است، بنابراین هر مسیری که از B می‌گذرد، باید طولانی‌تر از A به E باشد. بنابراین AE کوتاه‌ترین مسیر از A به E است.

توجه کنید که ما هنوز فاصله کوتاه‌ترین مسیری را که از A به B می‌رود، نمی‌دانیم. این مسیر ممکن است مسیر مستقیم AB با فاصله ۸ باشد. اما چون فاصله AE برابر ۱ است، ممکن است مسیر کوتاه‌تری به B از طریق E وجود داشته باشد. در این موقعیت، ما هنوز کمترین فاصله رسیدن به B را نمی‌دانیم و به همین دلیل است که این فاصله را موقتی می‌نامیم.

حال باید فاصله رسیدن به همسایه‌های بازدیدنشده E یعنی B، C و D را در صورتی که بتوان با هزینه کمتری از طریق E به آن‌ها رسید، به‌روزرسانی کنیم. در مورد راس B، فاصله AEB برابر با ۸ + ۱ = ۹ است و چون این عدد بیشتر از فاصله فعلی B که برابر با ۸ تنظیم شده می‌باشد، فاصله فعلی را تغییر نمی‌دهیم. تا این لحظه، فاصله موقتی C بی‌نهایت است، پس آن را با فاصله مسیر رسیدن به این راس از طریق E جایگزین می‌کنیم که همان AEC است. فاصله این مسیر برابر با ۱ + ۲ = ۳ است. به طور مشابه، فاصله موقتی D با AED جایگزین می‌شود که برابر با ۱ + ۷ = ۸ است. به این ترتیب جدول ما به صورت زیر درمی‌آید:

بازدید راس C

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

حال فاصله موقت همسایه‌های بازدیدنشده C را به‌روز می‌کنیم که B و D هستند. فاصله موقتی B از طریق C برابر با ۳ + ۳ = ۶ است. این فاصله از حاصل جمع فاصله اصلی C و وزن یال BC که هر دو برابر با ۳ هستند، بدست می‌آید. چون این فاصله جدید کمتر از فاصله قبلی B (۷) است، فاصل موقت B را به ۶ و راس قبلی‌اش را هم به C تنظیم می‌کنیم. فاصله موقتی D از طریق C برابر با ۳ + ۶ = ۹ است. چون این فاصله بیشتر از فاصله فعلی است، آن را تغییر نمی‌دهیم:

بازدید راس B

کار ما تقریباً تمام شده‌ است. در واقع اکنون تنها راس‌ها B و D بازدید نشده‌اند و B کوچک‌ترین فاصله موقتی را دارد، بنابراین آن را با فاصله واقعی ۶ به عنوان راس بازدید شده علامت می‌زنیم. B هیچ همسایه بازدیدنشده‌ای ندارد بنابراین در این مرحله کار دیگری نباید انجام دهیم:

بازدید راس D

اکنون تنها یک راس بازدیدنشده باقی مانده که D است. بنابراین آن را با فاصله واقعی ۸ (چون راه بهتری برای رسیدن به آن نیست) به عنوان بازدید شده علامت می‌زنیم. چون هیچ همسایه بازدید نشده‌ای از D نیز باقی نمانده، کار ما تمام است:

درخت کوتاه‌ترین مسیر

نتیجه اجرای الگوریتم دایجسترا یک درخت است که می‌تواند برای محاسبه مسیر و فاصله هر راس از راس مبدا، یعنی A استفاده شود. بنابراین، به عنوان مثال، کوتاه‌ترین مسیر رسیدن به D برابر با AED با فاصله ۸ است و کوتاه‌ترین مسیر رسیدن به B برابر با AECB با طول ۶ است:

باید توجه کنید که این درخت فقط برای مسیرهایی که از A شروع می‌شوند معتبر است. اگر از راس دیگری شروع کنیم، مسیری که این درخت نشان می‌دهد ممکن است کوتاه‌ترین نباشد. به عنوان مثال، اگر بخواهیم از C به D برویم، طبق این درخت باید از طریق E برویم که فاصله‌ای برابر با ۹ دارد. اما با نگاه به کل گراف، می‌بینیم که رفتن مستقیم از C به D با فاصله ۶ امکان‌پذیر است.

مرتبه زمانی الگوریتم دایجسترا

پیچیدگی زمانی این الگوریتم به ساختار داده‌ای که برای پیاده‌سازی آن استفاده می‌شود، وابسته است. در ادامه، پیچیدگی زمانی الگوریتم دایجسترا با استفاده از ساختارهای داده مختلف را بررسی می‌کنیم:

استفاده از هیپ دودویی

هنگامی که از هیپ دودویی (Binary Heap) برای پیاده‌سازی صف اولویت در الگوریتم دایجسترا استفاده شود، پیچیدگی زمانی الگوریتم به صورت زیر خواهد بود:

• مرحله‌ی ابتدایی: زمان لازم برای مقداردهی اولیه صف اولویت با V راس برابر است با O(V).
• عملیات حذف راس با حداقل فاصله: این عملیات برای هر راس یک بار انجام می‌شود و زمان لازم برای هر بار حذف برابر با O(logV) است، بنابراین در کل برابر با O(VlogV) خواهد بود.
• عملیات به‌روزرسانی فواصل: این عملیات برای هر یال یک بار انجام می‌شود و زمان لازم برای هر بار به‌روزرسانی برابر با O(logV) است. بنابراین در کل برای E یال، برابر با O(ElogV) خواهد بود.

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

O((V + E) \log V) = O(E \log V)

استفاده از فیبوناچی هیپ

اگر از هیپ فیبوناچی (Fibonacci Heap) برای پیاده‌سازی صف اولویت استفاده شود، پیچیدگی زمانی الگوریتم بهبود می‌یابد:

• مرحله‌ی ابتدایی: زمان لازم برای مقداردهی اولیه صف اولویت با V راس برابر است با O(V).
• عملیات حذف راس با حداقل فاصله: این عملیات برای هر راس یک بار انجام می‌شود و زمان لازم برای هر بار حذف برابر با O(logV) است، بنابراین در کل برابر با O(VlogV) خواهد بود.
• عملیات به‌روزرسانی فواصل: این عملیات برای هر یال E یک بار انجام می‌شود و زمان لازم برای هر بار به‌روزرسانی برابر با O(1) است. بنابراین در کل برابر با O(E) خواهد بود.

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

O(V \log V + E)

پیاده‌سازی الگوریتم دایجسترا در پایتون

برای محاسبه کوتاه‌ترین مسیر از یک راس به سایر راس‌ها با استفاده از الگوریتم دایجسترا، یک تابع به نام dijkstra تعریف می‌کنیم. در این تابع ابتدا، فاصله تمامی راس‌ها از راس مبدا به بی‌نهایت تنظیم کرده و فاصله راس مبدا به خودش را برابر صفر قرار می‌دهیم. سپس یک مجموعه sptSet برای نگهداری راس‌ها بازدیدشده ایجاد می‌کنیم. در ادامه و در هر تکرار حلقه for، راسی را که کمترین فاصله را از راس مبدا دارد و هنوز بازدید نشده، انتخاب و به sptSet اضافه می‌کنیم. برای هر همسایه این راس، اگر فاصله جدید کمتر از فاصله قبلی‌اش باشد، مقدار فاصله به‌روز می‌شود. این فرآیند تا زمانی که همه راس‌ها بازدید شوند ادامه می‌یابد و در نهایت فاصله‌های کوتاه‌ترین مسیر از راس مبدا به همه راس‌ها بازگردانده می‌شود:

def dijkstra(graph, source):
    # Initialize distances from the source to all vertices as infinity
    # except the source itself which is set to zero
    dist = {vertex: float('infinity') for vertex in graph}
    dist[source] = 0
    # Set to keep track of vertices included in the shortest path tree
    sptSet = set()

    # Loop until all vertices are processed
    while len(sptSet) < len(graph):
        # Select the vertex with the minimum distance value
        u = min((vertex for vertex in dist if vertex not in sptSet), key=dist.get)
        # Add the selected vertex to the set
        sptSet.add(u)

        # Update distance value of the adjacent vertices
        for neighbor, weight in graph[u].items():
            # If the vertex is not in the shortest path tree
            if neighbor not in sptSet:
                # Update the distance if the new distance is shorter
                if dist[u] + weight < dist[neighbor]:
                    dist[neighbor] = dist[u] + weight

        # Print the current state of distances
        print(f'{u} as minimum', ': ', dist)

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

graph = {
    'A': {'B': 7, 'E': 1},
    'B': {'A': 7, 'C': 3, 'E': 8},
    'C': {'B': 3, 'E': 2, 'D': 6},
    'D': {'C': 6, 'E': 7},
    'E': {'A': 1, 'B': 8, 'C': 2, 'D': 7}
}

dijkstra(graph, 'A')

A as minimum:
{‘A’: 0, ‘B’: 7, ‘C’: inf, ‘D’: inf, ‘E’: 1}
E as minimum:
{‘A’: 0, ‘B’: 7, ‘C’: 3, ‘D’: 8, ‘E’: 1}
C as minimum:
{‘A’: 0, ‘B’: 6, ‘C’: 3, ‘D’: 8, ‘E’: 1}
B as minimum:
{‘A’: 0, ‘B’: 6, ‘C’: 3, ‘D’: 8, ‘E’: 1}
D as minimum:
{‘A’: 0, ‘B’: 6, ‘C’: 3, ‘D’: 8, ‘E’: 1}

الگوریتم بلمن-فورد

الگوریتم بلمن-فورد (Bellman-Ford Algorithm) نیز مانند دایجسترا برای یافتن کوتاه‌ترین مسیر در گراف وزن‌دار استفاده می‌شود، با این تفاوت که می‌تواند وزن‌های منفی را نیز مدیریت کند. بلمن-فورد همچنین می‌تواند وجود دور منفی (دوری با وزن منفی) را در گراف تشخیص داده و آن را اعلام کند. این الگوریتم یک الگوریتم برنامه‌نویسی پویا (Dynamic Programming) است که چندین بار از روی تمام یال‌ها عبور می‌کند تا کوتاه‌ترین مسیرها را به‌روزرسانی کند.

تاریخچه الگوریتم بلمن-فورد

الگوریتم بلمن-فورد به طور مستقل توسط دو دانشمند به نام‌های ریچارد بلمن (Richard Bellman) و لستر فورد (Lester Ford) در دهه ۱۹۵۰ توسعه یافت. بلمن و فورد هر دو به طور مستقل در زمینه بهینه‌سازی و برنامه‌نویسی پویا کار می‌کردند و الگوریتم بلمن-فورد نتیجه تلاش‌های آن‌ها برای حل مسائل بهینه‌سازی در گراف‌ها بود. این الگوریتم به دلیل قابلیت مدیریت وزن‌های منفی در گراف‌ها، به سرعت جایگاه خود را در کاربردهای مختلف پیدا کرد.

الگوریتم بلمن-فورد چطور کار می‌کند؟

پیش از توضیح روند اجرای الگوریتم بلمن-فورد، بیایید با مفهوم دور منفی در گراف‌های وزن‌دار آشنا شویم:

دور منفی

دور منفی (Negative Cycle) یک چرخه در گراف است که وقتی وزن یال‌های آن جمع می‌شود، نتیجه منفی است. به عبارت دیگر، اگر از یک راس شروع کرده و در نهایت به همان راس بازگردیم و مجموع وزن‌های یال‌های طی شده منفی باشد، آن را دور منفی می‌نامیم.

تأثیر دور منفی بر الگوریتم‌های مسیریابی

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

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

• ابتدا فاصله راس مبدا تا خودش را به صفر و تا سایر راس‌ها را به بی‌نهایت (∞) مقداردهی می‌کنیم.
• سپس تمامی یال‌های گراف را به تعداد راس‌ها گراف منهای یک (n-1) بار مرور می‌کنیم.
• در هر بار، برای هر یال (u, v) با وزن w، اگر فاصله از مبدا به u به علاوه وزن w کمتر از فاصله فعلی از مبدا به v باشد، فاصله از مبدا به v را به‌روزرسانی می‌کنیم. به این عمل relax کردن یا آرام‌سازی یال‌ها می‌گوییم که n-1 بار انجام می‌شود.
• در مرحله بعد، یک بار دیگر برای nامین بار، تمامی یال‌ها را مرور می‌کنیم تا بررسی کنیم آیا فاصله‌ها تغییر می‌کنند یا خیر. اگر در این مرحله فاصله‌ها تغییر کنند، نشان‌دهنده وجود یک دور منفی در گراف است.

دقت کنید که در الگوریتم بلمن-فورد در هر بار اجرای عملیات آرام‌سازی همه یال‌ها (با یک ترتیب ثابت) بررسی می‌شوند.

خروجی الگوریتم بلمن-فورد چیست؟

خروجی الگوریتم بلمن-فورد شامل دو بخش است:

• کوتاه‌ترین فاصله‌ها از راس مبدا: الگوریتم بلمن-فورد فاصله کوتاه‌ترین مسیر از راس مبدا به هر یک از راس‌ها دیگر گراف را محاسبه می‌کند. این فاصله‌ها به‌صورت یک دیکشنری یا لیست نمایش داده می‌شوند که در آن کلیدها راس‌ها و مقادیر، فاصله‌های محاسبه‌شده هستند.
• تشخیص دورهای منفی: اگر در گراف یک دور منفی وجود داشته باشد، الگوریتم بلمن-فورد می‌تواند آن را تشخیص دهد. این کار با مرور دوباره تمامی یال‌ها بعد از n-1 تکرار انجام می‌شود. اگر در این مرور نهایی، فاصله‌ها همچنان تغییر کنند، نشان‌دهنده وجود یک دور منفی در گراف است.

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

برای بررسی گام‌به‌گام این الگوریتم، فرض کنید می‌خواهیم کوتاه‌ترین مسیر در گراف را از راس مبدا P را در شکل زیر بدست آوریم:

مقداردهی اولیه

ابتدا راس P را به عنوان نقطه شروع یا راس مبدا انتخاب می‌کنیم. سپس فاصله راس P تا همه راس‌ها را به بی‌نهایت و تا خودش را به صفر تنظیم می‌کنیم. برای سادگی پیگیری تغییرات فاصله‌ها در طول اجرای الگوریتم، از یک جدول استفاده می‌کنیم که مشابه جدول استفاده شده در الگوریتم دایجسترا است. در این جدول، فواصل به صورت موقت ثبت شده و در طی فرآیند آرام‌سازی یال‌ها، به‌روزرسانی می‌شوند:

ما در این مثال ترتیب آرام‌سازی یال‌ها را به صورت در نظر می‌گیریم:

1. (Q, S)

2. (T, S)

3. (R, S)

4. (R, T)

5. (P, Q)

6. (P, R)

توجه کنید که در هر دور آرام‌سازی یال‌ها به همین ترتیب آرام می‌شوند.

آرام‌سازی اول

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

• آرام‌سازی یال (Q, S): چون فاصله P تا Q بی‌نهایت و فاصله آن تا S نیز بی‌نهایت است، فاصله راس S از P بدون تغییر باقی می‌ماند.
• آرام‌سازی یال (T, S): چون فاصله P تا T بی‌نهایت و فاصله آن تا S نیز بی‌نهایت است، فاصله راس S از P بدون تغییر باقی می‌ماند.
• آرام‌سازی یال (R, S): چون فاصله P تا R بی‌نهایت و فاصله آن تا S نیز بی‌نهایت است، فاصله راس S از P بدون تغییر باقی می‌ماند.
• آرام‌سازی یال (R, T): چون فاصله P تا R بی‌نهایت و فاصله آن تا T نیز بی‌نهایت است، فاصله راس T از P بدون تغییر باقی می‌ماند.
• آرام‌سازی یال (P, Q): چون فاصله راس P تا خودش برابر با صفر و فاصله فعلی P تا Q بی‌نهایت است، اما فاصله مستقیم این دو راس ۲ واحد است، اگر از P به Q برویم، فاصله آن برابر با ۰ + ۲ = ۲ خواهد بود. چون این عدد کمتر از بی‌نهایت است، فاصله راس Q از P به ۲ تغییر می‌کند.
• آرام‌سازی یال (P, R): چون فاصله راس P تا خودش برابر با صفر و فاصله فعلی P تا R بی‌نهایت است، اما فاصله مستقیم این دو راس ۴ واحد است، اگر از P به R برویم، فاصله آن برابر با ۰ + ۴ = ۴ خواهد بود. چون این عدد کمتر از بی‌نهایت است، فاصله راس R از P به ۴ تغییر می‌کند.

آرام‌سازی دوم

• با اتمام دور اول آرام‌سازی، یک دور همه یال‌ها relax شدند و حال برای دومین بار این فرآیند را تکرار می‌کنیم:
• آرام‌سازی یال (Q, S): چون فاصله P تا Q برابر با ۲ واحد و فاصله فعلی P تا S بی‌نهایت است، اما فاصله مستقیم Q تا S برابر ۲ واحد است، اگر از P به Q و سپس به S برویم، فاصله آن برابر با ۲ + ۲ = ۴ خواهد بود. چون این عدد کمتر از بی‌نهایت است، فاصله راس S از P به ۴ تغییر می‌کند.
• آرام‌سازی یال (T, S): در این لحظه فاصله P تا T بی‌نهایت، فاصله آن تا S برابر ۴ واحد و فاصله مستقیم T تا S برابر ۵- است. اگر بخواهیم از طریق T به S برویم چون فاصله P تا T بی‌نهایت است، این عدد با ۵- جمع شده و حاصل باز هم بزرگتر از ۴ خواهد بود. لذا فاصله راس S از P دیگر تغییر نمی‌کند.
• آرام‌سازی یال (R, S): چون فاصله P تا R برابر ۴ واحد، فاصله آن تا S برابر ۴ واحد و فاصله مستقیم R تا S نیز برابر ۴ است، اگر بخواهیم از طریق R به S برویم، فاصله آن برابر با ۴ + ۴ = ۸ خواهد بود که بزرگتر از ۴ استو لذا فاصله راس S از P دیگر تغییر نخواهد کرد.
• آرام‌سازی یال (R, T): چون فاصله P تا R برابر ۴ واحد، فاصله آن تا T بی‌نهایت و فاصله مستقیم R تا T برابر ۳ واحد است، اگر بخواهیم از طریق R به T برویم، فاصله آن برابر با ۳ + ۴ = ۷ خواهد بود. چون این عدد کمتر از بی‌نهایت است، فاصله راس T از P به ۷ تغییر می‌کند.
• آرام‌سازی یال (P, Q): فاصله فعلی از P تا  Qبرابر ۲ واحد است و فاصله مستقیم نیز برابر ۲ واحد است، بنابراین فاصله P تا Q تغییری نخواهد کرد.
• آرام‌سازی یال (P, R): فاصله فعلی از P تا R برابر ۴ واحد است و فاصله مستقیم نیز برابر ۴ واحد است، بنابراین فاصله P تا R تغییری نخواهد کرد.

آرام‌سازی سوم

در دور سوم، دوباره تمام یال‌ها را بررسی می‌کنیم:

• آرام‌سازی یال (Q, S): فاصله از P تا Q برابر ۲ واحد است و فاصله فعلی از P تا S برابر ۴ واحد است و فاصله مستقیم Q تا S نیز برابر ۲ واحد است. اگر از P به Q و سپس به S برویم، فاصله آن برابر با ۲ + ۲ = ۴ خواهد بود. بنابراین فاصله S تغییری نمی‌کند.
• آرام‌سازی یال (T, S): فاصله از P تا T برابر ۷ واحد و فاصله مستقیم T تا S برابر ۵- است. اگر از P به T و سپس به S برویم، فاصله آن برابر با خواهد بود. چون ۲ کمتر از ۴ است، فاصله S از P به ۲ تغییر می‌کند.
• آرام‌سازی یال (R, S): فاصله فعلی P تا S برابر ۲ واحد است و فاصله مستقیم R تا S نیز برابر ۴ واحد است. از آنجایی که فاصله فعلی کمتر از مسیر جایگزین است، فاصله‌ S تغییری نمی‌کند.
• آرام‌سازی یال (R, T): فاصله از P تا R برابر ۴ واحد است و فاصله مستقیم R تا T برابر ۳ واحد است. از آنجایی که جمع این دو برابر ۷ است و با فاصله‌ فعلی T برابر است، فاصله‌ T تغییری نمی‌کند.
• آرام‌سازی یال (P, Q): فاصله فعلی از P تا Q برابر ۲ واحد است و فاصله‌ مستقیم نیز برابر ۲ واحد است، بنابراین فاصله P تا Q تغییری نخواهد کرد.
• آرام‌سازی یال (P, R): فاصله فعلی از P تا R برابر ۴ واحد است و فاصله‌ مستقیم نیز برابر ۴ واحد است، بنابراین فاصله‌ P تا R تغییری نخواهد کرد.

آرام‌سازی چهارم

در دور چهارم، همه یال‌ها یک بار دیگر بررسی می‌شوند:

• آرام‌سازی یال (Q, S): فاصله فعلی از P تا Q برابر ۲ واحد است و فاصله مستقیم Q تا S نیز برابر ۲ واحد است. چون فاصله فعلی کمتر یا مساوی با مسیر جایگزین است، فاصله S تغییری نمی‌کند.
• آرام‌سازی یال (T, S): فاصله فعلی از P تا T برابر ۷ واحد است و فاصله مستقیم T تا S برابر ۵- است. چون فاصله فعلی کمتر یا مساوی با مسیر جایگزین است، فاصله S تغییری نمی‌کند.
• آرام‌سازی یال (R, S): فاصله فعلی از P تا S برابر ۲ واحد است و فاصله مستقیم R تا S نیز برابر ۴ واحد است. چون فاصله فعلی کمتر از مسیر جایگزین است، فاصله S تغییری نمی‌کند.
• آرام‌سازی یال (R, T): فاصله فعلی از P تا R برابر ۴ واحد است و فاصله مستقیم R تا T برابر ۳ واحد است. چون فاصله فعلی کمتر یا مساوی با مسیر جایگزین است، فاصله T تغییری نمی‌کند.
• آرام‌سازی یال (P, Q): فاصله فعلی از P تا Q برابر ۲ واحد است و فاصله مستقیم نیز برابر ۲ واحد است، بنابراین فاصله P تا Q تغییری نخواهد کرد.
• آرام‌سازی یال (P, R): فاصله فعلی از P تا R برابر ۴ واحد است و فاصله مستقیم نیز برابر ۴ واحد است، بنابراین فاصله P تا R تغییری نخواهد کرد.

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

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

پیچیدگی زمانی الگوریتم بلمن-فورد به تعداد راس‌ها و یال‌های گراف وابسته است که در ادامه آن‌ها را بررسی می‌کنیم:

• مقداردهی اولیه: مقداردهی اولیه فاصله‌ها برای V راس، به زمان O(V) نیاز دارد.
• آرام‌سازی یال‌ها: این کار برای V−1 بار (تعداد راس‌ها منهای یک) تکرار می‌شود و برای گرافی با E یال، زمان لازم برای هر تکرار O(E) است که در کل می‌شود O(V⋅E).
• بررسی وجود چرخه‌های منفی: برای این کار یک بار تمام یال‌ها آرام‌سازی می‌شوند که به O(E) زمان نیاز دارد.

با جمع‌بندی مراحل فوق، پیچیدگی زمانی کلی الگوریتم بلمن-فورد برابر است با:

O(V \cdot E)

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

برای محاسبه کوتاه‌ترین مسیر در گراف از یک راس به سایر راس‌ها با استفاده از الگوریتم بلمن-فورد، یک تابع به نام bellman_ford تعریف می‌کنیم. در این تابع ابتدا، فاصله تمامی راس‌ها از راس مبدا به بی‌نهایت تنظیم می‌شود و فاصله راس مبدا به خودش برابر صفر قرار داده می‌شود. در مرحله بعد، در هر تکرار حلقه for که به تعداد راس‌ها (n) منهای یک بار اجرا می‌شود، برای هر راس و همسایه‌هایش بررسی می‌شود که آیا مسیر از طریق این راس به همسایه کوتاه‌تر است یا خیر؛ اگر کوتاه‌تر باشد، فاصله به این عدد تغییر می‌کند. در نهایت، بعد از n-1 بار اجرای فرآیند آرام‌سازی یال‌ها، یک بار دیگر (برای بار nم) همه یال‌ها بررسی می‌شوند تا ببینیم آیا هنوز می‌توان فاصله‌ها را کاهش داد یا خیر؛ اگر چنین باشد، به این معناست که گراف دارای دور منفی است و کوتاه‌ترین مسیر وجود ندارد:

def bellman_ford(graph, source):
     #Initialize distances from the source to all vertices as infinity
     #except the source itself which is set to zero.
    dist = {vertex: float('infinity') for vertex in graph}
    dist[source] = 0

     #Define the order of vertices
    vertices = sorted(graph.keys())

     #Relax edges repeatedly
    for i in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if dist[vertex] + weight < dist[neighbor]:
                    dist[neighbor] = dist[vertex] + weight
        print(i, 'round of relaxation: ', {v: dist[v] for v in vertices})

     #Check for negative weight cycles
    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if dist[vertex] + weight < dist[neighbor]:
                print("Graph contains a negative weight cycle")

نتیجه اجرای الگوریتم بلمن-فورد را روی گرافی که در مثال بالا بررسی کردیم به شکل زیر می‌توان دید:

graph = {
    'Q': {'S': 2},
    'T': {'S': -5},
    'S': {},
    'R': {'S': 4, 'T': 3},
    'P': {'Q': 2, 'R': 4}
}

bellman_ford(graph, 'P')

0 round of relaxation:
{‘P’: 0, ‘Q’: 2, ‘R’: 4, ‘S’: inf, ‘T’: inf}
1 round of relaxation:
{‘P’: 0, ‘Q’: 2, ‘R’: 4, ‘S’: 4, ‘T’: 7}
2 round of relaxation:
{‘P’: 0, ‘Q’: 2, ‘R’: 4, ‘S’: 2, ‘T’: 7}
3 round of relaxation:
{‘P’: 0, ‘Q’: 2, ‘R’: 4, ‘S’: 2, ‘T’: 7}

کوتاه‌ترین مسیرهای هم‌مبدا در DAG

گراف‌های جهت‌دار بدون دور (Directed Acyclic Graphs – DAGs) نوع خاصی از گراف‌ها هستند که در آن‌ها چرخه‌ای وجود ندارد. برای یافتن کوتاه‌ترین مسیر در این نوع گراف‌ها، از الگوریتم‌های خاصی استفاده می‌شود که در یکی از مهم‌ترین آن‌ها ابتدا گراف با استفاده از مرتب‌سازی توپولوژیکی (Topological Sort) مرتب می‌شود. سپس تک‌تک راس‌ها را به ترتیب توپولوژیکی پردازش می‌کنیم. برای هر راس که پردازش می‌شود، فاصله‌های راس‌های مجاور آن با استفاده از فاصله راس فعلی به‌روز می‌شود.

تاریخچه الگوریتم کوتاه‌ترین مسیرهای هم‌مبدا در DAG

الگوریتم پیدا کردن کوتاه‌ترین مسیر در گراف جهت‌دار بدون دور (DAG) به عنوان یک مسئله خاص در نظریه گراف‌ها شناخته می‌شود. این الگوریتم بر اساس مرتب‌سازی توپولوژیکی (Topological Sort) بنا شده است که اولین بار توسط رابرت تارژان (Robert Tarjan) در دهه ۱۹۷۰ معرفی شد. الگوریتم‌های مرتبط با DAG به دلیل ساختار خاص و کارایی بالایشان در حل مسائل بهینه‌سازی در گراف‌های جهت‌دار بدون دور، مورد توجه محققان قرار گرفته‌اند.

کوتاه‌ترین مسیرهای هم‌مبدا در DAG را چطور می‌توان بدست آورد؟

برای اجرای این الگوریتم مراحل زیر را به ترتیب انجام می‌دهیم:

• ابتدا فاصله تمامی راس‌ها از راس مبد را به بی‌نهایت (infinity) مقداردهی می‌کنیم و فاصله راس مبدا به خودش را صفر قرار می‌دهیم.
• در گام بعدی، یک مرتب‌سازی توپولوژیکی روی گراف انجام می‌دهیم تا یک ترتیب خطی از راس‌های گراف به دست آوریم. این ترتیب تضمین می‌کند که هر راس قبل از راس‌های مجاورش بازدید می‌شود.
• راس‌ها را به ترتیب توپولوژیکی یکی یکی پردازش می‌کنیم. برای هر راس پردازش‌شده، فاصله‌های راس‌های مجاور آن را با استفاده از فاصله فعلی راس به‌روز می‌کنیم. اگر فاصله جدید کوتاه‌تر از فاصله قبلی باشد، مقدار فاصله به این عدد تغییر می‌کند.

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

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

تنظیم اولیه فاصله‌ها و مرتب‌سازی توپولوژیکی

در ابتدا، فاصله تمامی راس‌ها از راس مبدا به بی‌نهایت و فاصله راس مبدا تا خودش به صفر تنظیم می‌شود. ما در این مثال راس s را به عنوان راس مبدا در نظر می‌گیریم. سپس راس‌های گراف را به ترتیب توپولوژیکی آن مرتب می‌کنیم. در این مثال، یکی از ترتیب‌های ممکن به شکل زیر است:

r \rightarrow s \rightarrow t \rightarrow x \rightarrow y \rightarrow z

می‌توان برای سادگی و درک بهتر روند الگوریتم، شکل گراف را به همین ترتیب رسم و فاصله راس مبدا تا هر راس را روی آن نشان دهیم:

پردازش راس‌های r و s

در این مرحله باید راس‌ها را به ترتیب توپولوژیکی بدست آمده، پردازش ‌کنیم. برای این منظور ابتدا راس r را که اولین راس در ترتیب توپولوژیکی است، پردازش می‌کنیم. چون فاصله راس s تا این راس بی‌نهایت است (کلا هم راهی برای رسیدن از راس s به r وجود ندارد و این عدد تا پایان الگوریتم بی‌نهایت خواهد ماند)، مجموع این عدد به علاوه وزن یال این راس تا رئوس همسایه‌اش، باز هم بی‌نهایت خواهد شد. به همین دلیل فاصله هیچ راسی از طریق r به‌روزرسانی نمی‌شود.

سپس راس s را پردازش می‌کنیم. چون فاصله راس s تا خودش برابر صفر و وزن یال st برابر ۲ است، فاصله این راس تا راس t برابر ۰ + ۲ = ۲ خواهد بود. این عدد کمتر از فاصله فعلی s تا t (بی‌نهایت) است و در نتیجه این فاصله را به ۲ تغییر خواهیم داد. همچنین چون وزن یال sx برابر ۶ واحد است، فاصله این راس تا راس x برابر ۰ + ۶ = ۶ خواهد بود. این عدد هم کمتر از فاصله فعلی s تا x (بی‌نهایت) است و در نتیجه این فاصله را به عدد ۶ تغییر خواهیم داد:

پردازش راس t

حال راس t را پردازش می‌کنیم. در این مرحله، چون فاصله s تا t برابر ۲ است و وزن یال t به x برابر ۷ است، فاصله از s تا x از طریق راس t برابر۲ + ۷ = ۹ می‌شود. این مقدار کمتر از فاصله فعلی x (۶) نیست، بنابراین تغییری در فاصله s به x ایجاد نمی‌شود.

اما وزن یال t به y برابر ۴ است و چون فاصله s تا t برابر ۲ واحد است، فاصله s تا y از طریق راس t برابر با ۲ + ۴ = ۶ می‌شود که کمتر از فاصله فعلی y (بی‌نهایت) است. در نتیجه این فاصله را به عدد ۶ تغییر می‌دهیم.

همچنین وزن یال t به z برابر ۲ است و چون فاصله از s تا z برابر ۲ واحد است، فاصله s تا z از طریق راس t برابر با ۲ + ۲ = ۴ می‌شود که کمتر از فاصله فعلی z (بی‌نهایت) است. در نتیجه این فاصله را به عدد ۴ تغییر می‌دهیم:

پردازش راس x

حال راس x را پردازش می‌کنیم. در این مرحله، چون فاصله s تا x برابر ۶ و وزن یال x به y برابر ۱- است، فاصله از s تا y از طریق راس x برابر ۱ – ۶ = ۵ می‌شود. این مقدار کمتر از فاصله فعلی y (۶) است و در نتیجه این فاصله را به ۵ تغییر می‌دهیم.

اما وزن یال x به z برابر ۱ است و چون فاصله s تا x برابر ۶ واحد است، فاصله s تا z از طریق راس x برابر با ۱ + ۶ = ۷ می‌شود که این مقدار کمتر از فاصله فعلی z (۴) نیست. بنابراین در این مرحله تغییری در فاصله s به z ایجاد نمی‌شود:

پردازش راس y

حال راس y را پردازش می‌کنیم. در این مرحله، چون فاصله s تا y برابر ۵ و وزن یال y به z برابر ۲- است، فاصله از s تا z از طریق راس y برابر ۲ – ۵ = ۳ می‌شود. این مقدار کمتر از فاصله فعلی z (۴) است و در نتیجه این فاصله را به ۳ تغییر می‌دهیم:

پردازش راس z

مرحله آخر پردازش راس z است که چون هیچ یالی از آن خارج نشده، تغییری در فاصله راس s تا راس‌های دیگر ایجاد نمی‌شود:

به این ترتیب فاصله کوتاه‌ترین مسیر از راس s تا همه راس‌های این گراف بدست می‌آید.

مرتبه زمانی الگوریتم پیدا کردن کوتاه‌ترین مسیرهای هم‌مبدا در DAG

همان‌طور که دیدید، این الگوریتم از ترتیب توپولوژیک گراف استفاده می‌کند که باعث می‌شود پیچیدگی زمانی آن خطی باشد:

• یافتن ترتیب توپولوژیکی: زمان لازم برای یافتن ترتیب توپولوژیکی که از الگوریتم جستجوی عمق اول استفاده می‌کند، برای گرافی با V راس و E یال برابر با O(V+E) است.
• مقداردهی اولیه: مقداردهی اولیه فاصله‌ها: در این الگوریتم به O(V) زمان نیاز دارد.
• به‌روزرسانی فاصله‌ها: این کار نیز در زمان خطی O(V+E) انجام می‌شود.

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

O(V + E)

پیاده‌سازی الگوریتم پیدا کردن کوتاه‌ترین مسیرهای هم‌مبدا در DAG

برای محاسبه کوتاه‌ترین مسیر از یک راس به سایر راس‌ها در یک گراف بدون دور با استفاده از الگوریتم کوتاه‌ترین مسیر DAG، یک تابع به نام dag_shortest_path تعریف می‌کنیم. در این تابع ابتدا، با استفاده از تابع مرتب‌سازی توپولوژیکی که در مقاله قبلی با کمک الگوریتم DFS آن را ساختیم، ترتیب توپولوژیکی راس‌ها را به دست می‌آوریم. سپس فاصله تمامی راس‌ها از راس مبدا به بی‌نهایت تنظیم می‌کنیم و فاصله راس مبدا به خودش را برابر صفر قرار می‌دهیم. در مرحله بعد، راس‌ها را به ترتیب توپولوژیکی که بدست آوردیم، پردازش می‌کنیم؛ برای هر راس و همسایه‌هایش بررسی می‌شود که آیا مسیر از طریق این راس به همسایه کوتاه‌تر است یا خیر و همان‌طور که گفتیم، اگر کوتاه‌تر باشد، فاصله به این عدد تغییر می‌کند. در نهایت، فاصله‌های کوتاه‌ترین مسیر از راس مبدا به سایر راس‌ها محاسبه شده و در هر مرحله از به‌روزرسانی فاصله‌ها چاپ می‌شود تا روند کار مشاهده شود:

def dfs(graph, start, visited=None, stack=None):
    # Initialize visited and stack if not provided
    if visited is None:
        visited = []
    if stack is None:
        stack = []
    # Mark the current node as visited
    visited.append(start)
    # Recur for all the vertices adjacent to this vertex
    for neighbor in graph[start]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited, stack)
    # Push current vertex to stack which stores the result
    stack.append(start)

def topological_sort(graph):
    visited = []
    stack = []
    # Call the recursive helper function to store
    # Topological Sort starting from all vertices one by one
    for node in graph:
        if node not in visited:
            dfs(graph, node, visited, stack)
    return stack[::-1]

def dag_shortest_path(graph, source):
    # Perform topological sort using DFS
    topological_order = topological_sort(graph)
    print(f'Topological sort: {topological_order}\n')

    # Initialize distances to all vertices as infinite
    dist = {vertex: float('infinity') for vertex in topological_order}
    dist[source] = 0

    # Process vertices in topological order
    for vertex in topological_order:
        for neighbor, weight in graph[vertex].items():
            if dist[vertex] + weight < dist[neighbor]:
                dist[neighbor] = dist[vertex] + weight
        print(f'Process node {vertex}: {dist}')

نتیجه اجرای الگوریتم پیدا کردن کوتاه‌ترین مسیرهای هم‌مبدا در DAG را روی گرافی که در مثال بالا بررسی کردیم به شکل زیر می‌توان دید:

graph = {
    's': {'t': 2, 'x': 6},
    'r': {'s': 5, 't': 3},
    't': {'x': 7, 'y': 4},
    'x': {'y': -1, 'z': 1},
    'y': {'z': -2},
    'z': {},
}

dag_shortest_path(graph, 's')

Topological sort:
[‘r’, ‘s’, ‘t’, ‘x’, ‘y’, ‘z’]

Process node r:
{‘r’: inf, ‘s’: 0, ‘t’: inf, ‘x’: inf, ‘y’: inf, ‘z’: inf}
Process node s:
{‘r’: inf, ‘s’: 0, ‘t’: 2, ‘x’: 6, ‘y’: inf, ‘z’: inf}
Process node t:
{‘r’: inf, ‘s’: 0, ‘t’: 2, ‘x’: 6, ‘y’: 6, ‘z’: inf}
Process node x:
{‘r’: inf, ‘s’: 0, ‘t’: 2, ‘x’: 6, ‘y’: 5, ‘z’: 7}
Process node y:
{‘r’: inf, ‘s’: 0, ‘t’: 2, ‘x’: 6, ‘y’: 5, ‘z’: 3}
Process node z:
{‘r’: inf, ‘s’: 0, ‘t’: 2, ‘x’: 6, ‘y’: 5, ‘z’: 3}

یافتن کوتاه‌ترین مسیرهای هم‌مبدا در گراف بدون وزن

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

جستجوی سطح اول

برای یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن، می‌توان از الگوریتم جستجوی سطح اول (Breadth First Search – BFS) استفاده کرد. الگوریتم BFS یک الگوریتم پیمایش گراف ساده است که با شروع از راس مبدا، به ترتیب تمام راس‌های همسایه را بازدید می‌کند و کوتاه‌ترین مسیرها به تمام راس‌های دیگر را در یک گراف بدون وزن محاسبه می‌کند.

کوتاه‌ترین مسیرهای هم‌مبدا را در گراف‌های بدون وزن چطور می‌توان بدست آورد؟

برای این منظور مراحل زیر را طی می‌کنیم:

• ابتدا یک صف خالی و یک آرایه برای نگه‌داری فاصله‌ی هر گره از منبع ایجاد می‌کنیم.
• گره‌ی شروع را به صف اضافه و فاصله آن را از راس مبدا صفر قرار می‌دهیم.
• تا زمانی که صف خالی نشده:
  • گره اول صف را از صف خارج می‌کنیم.
  • تمامی همسایه‌های گره‌ی خارج شده را بررسی می‌کنیم. اگر این همسایه‌ها هنوز بازدید نشده باشند، به صف اضافه می‌شوند و فاصله‌ی آن‌ها از راس مبدا برابر با فاصله‌ی گره‌ی فعلی به اضافه‌ی یک تنظیم می‌شود.

در نهایت، پس از اتمام کار، آرایه‌ی فاصله‌ها به ما نشان می‌دهد که کوتاه‌ترین فاصله از راس مبدا به هر راس چقدر است.

مرتبه زمانی الگوریتم جستجوی سطح اول برای پیدا کردن کوتاه‌ترین مسیر در گراف بی‌وزن

این الگوریتم به دلیل بررسی سطح به سطح و عدم نیاز به وزن‌های متفاوت برای یال‌ها، قادر است کوتاه‌ترین مسیر را از یک منبع واحد به تمامی رئوس دیگر در یک گراف بدون وزن را با پیچیدگی زمانی O(V+E) که در آن V تعداد راس‌ها و E تعداد یال‌ها است، پیدا کند. درواقع مرتبه زمانی اجرای این الگوریتم همان مرتبه زمانی الگوریتم BFS خواهد بود.

پیاده‌سازی الگوریتم جستجوی سطح اول برای کوتاه‌ترین مسیر در پایتون

برای این منظور تابعی به نام bfs_shortest_paths تعریف می‌کنیم که فاصله‌ راس مبدا تا سایر راس‌ها را محاسبه می‌کند. در این تابع، ابتدا یک دیکشنری به نام distances ایجاد می‌کنیم که فاصله‌ی هر راس (به عنوان کلید یا همان keys) از راس مبدا را نگه می‌دارد و تمامی مقادیر (values) آن را به بی‌نهایت تنظیم می‌کنیم. سپس فاصله‌ی راس مبدا را به صفر تنظیم کرده و راس مبدا را به صف اضافه می‌کنیم. سپس تا زمانی که صف خالی نشده، گره اول صف را از صف خارج می‌کنیم و تمامی همسایه‌های گره خارج شده را بررسی می‌کنیم. اگر این همسایه‌ها هنوز بازدید نشده باشند، به صف اضافه می‌شوند و فاصله‌ی آن‌ها از راس مبدا برابر با فاصله‌ی گره فعلی به اضافه‌ی یک تنظیم می‌شود. این فرآیند تا زمانی که صف خالی شود ادامه می‌یابد و در نهایت دیکشنری distances حاوی فاصله‌های کوتاه‌ترین مسیر از راس مبدا به تمامی راس‌های دیگر خواهد بود:

from collections import deque

def bfs_shortest_paths(graph, start):
    # Initialize distances to all vertices as infinity
    distances = {vertex: float('infinity') for vertex in graph}
    # Distance to the start vertex is set to 0
    distances[start] = 0
    # Initialize the queue with the start vertex
    queue = deque([start])

    # Process the queue until it is empty
    while queue:
        node = queue.popleft()
        # Iterate through neighbors of the current node
        for neighbor in graph[node]:
            # If the neighbor has not been visited, update the distance
            if distances[neighbor] == float('infinity'):
                queue.append(neighbor)
                distances[neighbor] = distances[node] + 1
                print(distances)

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

graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['A', 'B'],
    'E': ['C', 'F'],
    'F': ['E']
}

bfs_shortest_paths(graph, 'A')

{‘A’: 0, ‘B’: 1, ‘C’: inf, ‘D’: inf, ‘E’: inf, ‘F’: inf}
{‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: inf, ‘E’: inf, ‘F’: inf}
{‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: 1, ‘E’: inf, ‘F’: inf}
{‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: 1, ‘E’: 2, ‘F’: inf}
{‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: 1, ‘E’: 2, ‘F’: 3}

یافتن کوتاه‌ترین مسیر بین هر دو راس در گراف

همان‌طور که اشاره شد، یافتن کوتاه‌ترین مسیر بین هر دو راس در گراف‌ها الگوریتم‌های مختص به خود را دارد. اما این مسئله را نیز می‌توان براساس نوع گراف به دو زیر مسئله دیگر تبدیل کرد:

یافتن کوتاه‌ترین مسیر بین هر دو راس در گراف وزن‌دار

برای یافتن کوتاه‌ترین مسیر بین هر دو راس در گراف‌های وزن‌دار نیاز به الگوریتم‌های متفاوتی نسبت به دایجسترا و بلمن-فورد داریم، هرچند که می‌توان هر یک از این الگوریتم‌ها را V بار یعنی به تعداد کل راس‌ها گراف (هر بار با انتخاب یک راس جدید به عنوان راس شروع) اجرا کرد و به کوتاه‌ترین مسیر بین هر دو راس دست یافت اما این کار مرتبه زمانی این الگوریتم‌ها را V برابر می‌کند که چندان بهینه نیست. در عوض راه حل بهینه‌تری وجود دارد که در ادامه به آن‌ها اشاره می‌کنیم:

الگوریتم فلوید-وارشال

الگوریتم فلوید-وارشال (Floyd-Warshall Algorithm) یکی از معروف‌ترین الگوریتم‌ها برای یافتن کوتاه‌ترین مسیر بین هر دو راس در گراف‌های وزن‌دار است. این الگوریتم از رویکرد برنامه‌نویسی پویا استفاده می‌کند و با ایجاد یک ماتریس فاصله، به تدریج فاصله‌های کوتاه‌ترین مسیر بین همه جفت‌های راس‌ها را به‌روزرسانی می‌کند. این الگوریتم قادر به مدیریت یال‌هایی با وزن منفی نیز هست.

این الگوریتم معمولاً با نام‌های مختلفی شناخته می‌شود، از جمله:

• الگوریتم فلوید (Floyd’s Algorithm)
• الگوریتم روی-فلوید (Roy-Floyd Algorithm)
• الگوریتم روی-وارشال (Roy-Warshall Algorithm)
• الگوریتم فلوید-وارشال (Floyd-Warshall Algorithm)
• الگوریتم WFI (مخفف نام سه دانشمندانی که به توسعه این الگوریتم کمک کرده‌اند)

تاریخچه الگوریتم فلوید-وارشال

الگوریتم فلوید-وارشال توسط رابرت فلوید (Robert Floyd) و استیون وارشال (Stephen Warshall) به طور مستقل در دهه ۱۹۶۰ توسعه یافت. رابرت فلوید الگوریتم خود را در سال ۱۹۶۲ و استیون وارشال الگوریتم مشابهی را در همان سال برای حل مسائل گراف ارائه دادند. این الگوریتم‌ها از رویکرد برنامه‌نویسی پویا برای یافتن کوتاه‌ترین مسیر بین همه جفت‌های راس‌ها در یک گراف استفاده می‌کنند و به دلیل کارایی بالایشان به سرعت محبوبیت یافتند.

الگوریتم فلوید-وارشال چطور کار می‌کند؟

• برای اجرای الگوریتم فلوید-وارشال ابتدا یک ماتریس فاصله (Distance Matrix) برای تمامی زوج‌ راس‌ها ایجاد می‌کنیم. در این ماتریس، هر عنصر (i, j) نشان‌دهنده کوتاه‌ترین مسیر مستقیم یا غیرمستقیم بین رئوس i و j است.
• سپس این ماتریس فاصله را با مقادیر اولیه پر می‌کنیم. اگر یک یال مستقیم بین رئوس i و j وجود داشته باشد، وزن آن یال را در ماتریس قرار می‌دهیم. در غیر این صورت، مقدار بی‌نهایت در ماتریس قرار می‌گیرد. فاصله هر راس با خودش را نیز صفر در نظر گرفته می‌گیریم، یعنی درایه‌های روی قطر اصلی این ماتریس تمام صفر است.
• در این الگوریتم سه حلقه تو در تو داریم که هر یک از آن‌ها بر روی تمام رئوس گراف اجرا می‌شوند. با حلقه بیرونی راس میانی k را انتخاب می‌کنیم و با حلقه‌های درونی دو راس i و j را برای بررسی تمامی مسیرهای ممکن بین i و j از طریق k بررسی می‌کنیم.
• برای هر جفت راس (i, j) بررسی می‌کنیم که آیا مسیر عبور از k کوتاه‌تر از مسیر مستقیم بین  i و j است یا خیر. اگر چنین باشد، ماتریس فاصله را با استفاده از رابطه زیر به‌روزرسانی می‌کنیم:

\text{distance}[i][j] = \min(\text{distance}[i][j], \text{distance}[i][k] + \text{distance}[k][j])

• این فرایند را برای تمامی رئوس به عنوان راس میانی تکرار می‌کنیم تا زمانی که تمامی مسیرهای ممکن بررسی شوند و ماتریس فاصله نهایی به‌روز شود.

خروجی الگوریتم فلوید-وارشال

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

بررسی گام‌به‌گام مراحل اجرای الگوریتم فلوید-وارشال

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

ایجاد ماتریس فاصله اولیه

ابتدا ماتریس D₀ را ایجاد می‌کنیم که هر عنصر D[i][j] آن نشان‌دهنده فاصله مستقیم بین راس i و j است. در این گراف، فاصله‌های مستقیم به شرح زیر است:

• فاصله از راس ۱ به ۲ برابر با۵۲ است، پس در درایه (۱,۲) ماتریس عدد ۵ قرار می‌گیرد.
• فاصله از راس ۲ به ۱ برابر با ۵۰ است، پس در درایه (۲,۱) ماتریس عدد ۵۰ قرار می‌گیرد.
• فاصله از راس ۲ به ۳ برابر با ۱۵ است، پس در درایه (۲,۳) ماتریس عدد ۱۵ قرار می‌گیرد.
• فاصله از راس ۲ به ۴ برابر با ۵ است، پس در درایه (۲,۴) ماتریس عدد ۵ قرار می‌گیرد.
• فاصله از راس ۳ به ۱ برابر با ۳۰ است، پس در درایه (۳,۱) ماتریس عدد ۳۰ قرار می‌گیرد.
• فاصله از راس ۳ به ۴ برابر با ۱۵ است، پس در درایه (۴,۱) ماتریس عدد ۱۵ قرار می‌گیرد.
• فاصله از راس ۴ به ۱ برابر با ۱۵ است، پس در درایه (۳,۴) ماتریس عدد ۱۵ قرار می‌گیرد.
• فاصله از راس ۴ به ۳ برابر با ۵ است، پس در درایه (۴,۳) ماتریس عدد ۵ قرار می‌گیرد.

درایه‌های روی قطر اصلی همان‌طور که گفتیم برابر صفر و سایر درایه‌های ماتریس برابر بی‌نهایت قرار می‌گیرند:

به‌روزرسانی با راس واسطه یک

در این مرحله، ماتریس فاصله D₁ را با استفاده از راس یک به عنوان راس واسطه به‌روزرسانی می‌کنیم. فرمول به‌روزرسانی به این شکل است:

D_{1}[i,j]=\min(D_{0}[i,j],D_{0}[i,1]+D_{0}[1,j])

در این مرحله تنها فاصله رسیدن از راس‌های ۳ و ۴ به راس ۲ (از طریق راس  ۱) تغییر می‌کند. زیرا در حال حاضر فاصله رسیدن از راس ۳ به راس ۲ برابر بی‌نهایت است اما اگر ابتدا از راس ۳ به ۱ برویم و سپس از راس ۱ به ۲ برویم، این فاصله به ۳۵ خواهد رسید. چون این عدد کمتر از بی‌نهایت است، پس فاصله راس ۳ به ۲ به‌روزرسانی می‌شود؛ یعنی:

D_{1}[3,2]=\min(D_{0}[3,2],D_{0}[3,1]+D_{0}[1,2]) \rightarrow D_{1}[3,2]=\min( \infty, 30 + 5) = 35

همچنین فاصله فعلی راس ۴ به ۲ برابر بی‌نهایت است اما اگر ابتدا از راس ۴ به ۱ برویم و سپس از راس ۱ به ۲ برویم، این فاصله به ۲۰ خواهد رسید. چون این عدد کمتر از بی‌نهایت است، پس فاصله راس ۳ به ۲ به‌روزرسانی می‌شود؛ یعنی:

D_{1}[4,2]=\min(D_{0}[4,2],D_{0}[4,1]+D_{0}[1,2]) \rightarrow D_{1}[4,2]=\min( \infty, 15 + 5) = 20

سایر درایه‌های این ماتریس در این مرحله دستخوش تغییر نمی‌شوند زیرا فاصله فعلی‌شان کمتر از مسیری است که از راس یک بگذرد؛ مثلا فاصله راس ۲ تا ۴ که در حال حاضر برابر ۵ است اما اگر بخواهیم از ۲ به ۱ برویم فاصله‌ای برابر ۵۰ دارد و فاصله رسیدن از ۱ به ۴ بی‌نهایت است. در نتیجه برای رفتن از ۲ به ۴ از طریق راس ۱ فاصله بیشتر از فاصله فعلی این دو راس خواهد شد و به همین دلیل تغییر نمی‌کند؛ یعنی:

D_{1}[2,4]=\min(D_{0}[2,4],D_{0}[2,1]+D_{0}[1,4]) \rightarrow D_{1}[2,4]=\min( 5, 50 + \infty) = 5

به این ترتیب ماتریس فاصله D₁ به صورت زیر خواهد بود:

به‌روزرسانی با راس واسطه دو

در این مرحله، ماتریس فاصله D₂ را با استفاده از راس دو به عنوان راس واسطه به‌روزرسانی می‌کنیم. فرمول به‌روزرسانی به این شکل است:

D_{2}[i,j]=\min(D_{1}[i,j],D_{1}[i,2]+D_{1}[2,j])

در این مرحله تنها فاصله رسیدن از راس ۱ به راس‌های ۳ و ۴ (از طریق راس ۲) تغییر می‌کند. زیرا در حال حاضر فاصله رسیدن از راس ۱ به راس ۳ برابر بی‌نهایت است اما اگر ابتدا از راس ۱ به ۲ برویم و سپس از راس ۲ به ۳ برویم، این فاصله به ۲۰ خواهد رسید. چون این عدد کمتر از بی‌نهایت است، پس فاصله راس ۱ به ۳ به‌روزرسانی می‌شود؛ یعنی:

D_{2}[1,3]=\min(D_{1}[1,3],D_{1}[1,2]+D_{1}[2,3]) \rightarrow D_{2}[1,3]=\min(\infty, 5 + 15) = 20

همچنین فاصله فعلی راس ۱ به ۴ برابر بی‌نهایت است اما اگر ابتدا از راس ۱ به ۲ برویم و سپس از راس ۲ به ۴ برویم، این فاصله به ۱۰ خواهد رسید. چون این عدد کمتر از بی‌نهایت است، پس فاصله راس ۱ به ۴ به‌روزرسانی می‌شود؛ یعنی:

D_{2}[1,4]=\min(D_{1}[1,4],D_{1}[1,2]+D_{1}[2,4]) \rightarrow D_{2}[1,4]=\min(\infty, 5+ 5) = 10

سایر درایه‌های این ماتریس در این مرحله دستخوش تغییر نمی‌شوند زیرا فاصله فعلی‌شان کمتر از مسیری است که از راس یک بگذرد. به این ترتیب ماتریس فاصله D₂ به صورت زیر خواهد بود:

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

در این مرحله، ماتریس فاصله D₃ را با استفاده از راس سه به عنوان راس واسطه به‌روزرسانی می‌کنیم. فرمول به‌روزرسانی به این شکل است:

D_{3}[i,j]=\min(D_{2}[i,j],D_{2}[i,3]+D_{2}[3,j])

در این مرحله تنها فاصله رسیدن از راس ۲ به راس‌ ۱ (از طریق راس ۳) تغییر می‌کند. زیرا در حال حاضر فاصله رسیدن از راس ۲ به راس ۱ برابر ۵۰ است اما اگر ابتدا از راس ۲ به ۳ برویم و سپس از راس ۳ به ۱ برویم، این فاصله به ۴۵ خواهد رسید. چون این عدد کمتر از ۵۰ است، پس فاصله راس ۲ به ۱ به‌روزرسانی می‌شود؛ یعنی:

D_{3}[2,1]=\min(D_{2}[2,1],D_{2}[2,3]+D_{2}[3,1]) \rightarrow D_{3}[2,1]=\min(50, 15+ 30) = 45

سایر درایه‌های این ماتریس در این مرحله دستخوش تغییر نمی‌شوند زیرا فاصله فعلی‌شان کمتر از مسیری است که از راس یک بگذرد. به این ترتیب ماتریس فاصله D₃ به صورت زیر خواهد بود:

به‌روزرسانی با راس واسطه چهار

در این مرحله، ماتریس فاصله D₄ را با استفاده از راس چهار به عنوان راس واسطه به‌روزرسانی می‌کنیم. فرمول به‌روزرسانی به این شکل است:

D_{4}[i,j]=\min(D_{3}[i,j],D_{3}[i,4]+D_{3}[4,j])

در این مرحله فاصله رسیدن از راس ۲ به راس‌ ۱ و نیز راس‌های ۱ و ۲ به ۳ (از طریق راس ۴) تغییر می‌کند. زیرا در حال حاضر فاصله رسیدن از راس ۲ به راس ۱ برابر ۴۵ است اما اگر ابتدا از راس ۲ به ۴ برویم و سپس از راس ۴ به ۱ برویم، این فاصله به ۲۰ خواهد رسید. چون این عدد کمتر از ۴۵ است، پس فاصله راس ۲ به ۱ به‌روزرسانی می‌شود؛ یعنی:

D_{4}[2,1]=\min(D_{3}[2,1],D_{3}[2,4]+D_{3}[4,1]) \rightarrow D_{4}[2,1]=\min(45, 5 + 15) = 20

همچنین فاصله فعلی راس ۱ به ۳ برابر ۲۰ است اما اگر ابتدا از راس ۱ به ۴ برویم و سپس از راس ۴ به ۳ برویم، این فاصله به ۱۵ خواهد رسید. چون این عدد کمتر از ۲۰ است، پس فاصله راس ۱ به ۳ به‌روزرسانی می‌شود؛ یعنی:

D_{4}[1,3]=\min(D_{3}[1,3],D_{3}[1,4]+D_{3}[4,3]) \rightarrow D_{4}[1,3]=\min(20, 10 + 5) = 15

از طرفی فاصله فعلی راس ۲ به ۳ برابر ۱۵ است اما اگر ابتدا از راس ۲ به ۴ برویم و سپس از راس ۴ به ۳ برویم، این فاصله به ۱۰ خواهد رسید. چون این عدد کمتر از ۱۵ است، پس فاصله راس ۲ به ۳ به‌روزرسانی می‌شود؛ یعنی:

D_{4}[2,3]=\min(D_{3}[2,3],D_{3}[2,4]+D_{3}[4,3]) \rightarrow D_{4}[2,3]=\min(15, 5 + 5) = 10

سایر درایه‌های این ماتریس در این مرحله دستخوش تغییر نمی‌شوند زیرا فاصله فعلی‌شان کمتر از مسیری است که از راس یک بگذرد. به این ترتیب ماتریس فاصله D₄ به صورت زیر خواهد بود:

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

پیچیدگی زمانی الگوریتم فلوید-وارشال به دلیل استفاده از سه حلقه تودرتو برای به‌روزرسانی ماتریس فاصله‌ها برابر با  O(V³) است، که در آن V تعداد راس‌ها است. به این معنا که زمان اجرای الگوریتم به صورت مکعبی با افزایش تعداد راس‌ها افزایش می‌یابد.

پیاده‌سازی الگوریتم فلوید-وارشال در پایتون

برای محاسبه کوتاه‌ترین مسیر بین تمام جفت‌های راس‌ها با استفاده از الگوریتم فلوید-وارشال، ابتدا کتابخانه numpy را فراخوانی می‌کنیم. سپس تابعی به نام floyd_warshall تعریف می‌کنیم که graph را به صورت ماتریس مجاورت و به عنوان آرگومان ورودی دریافت می‌کند. در این تابع، تعداد راس‌ها از اندازه ماتریس استخراج و یک کپی از ماتریس گراف برای ذخیره فاصله‌ها ایجاد می‌شود. سپس سه حلقه تو در تو هر جفت راس (i, j) را با استفاده از هر راس واسطه (k) بررسی می‌کنند. اگر فاصله رسیدن از راس i به j از طریق راس k کوتاه‌تر از فاصله مسیر فعلی i به j باشد، فاصله بین رئوس i و j با فاصله از طریق راس k به‌روزرسانی می‌شود:

import numpy as np

def floyd_warshall(graph):
    # Number of vertices in the graph
    num_vertices = graph.shape[0]
    # Create a copy of the graph to store distances
    dist = graph.copy()

    # Apply Floyd-Warshall algorithm
    for k in range(num_vertices):
        for i in range(num_vertices):
            for j in range(num_vertices):
                # If the path through vertex k is shorter, update the distance
                if dist[i, j] > dist[i, k] + dist[k, j]:
                    dist[i, j] = dist[i, k] + dist[k, j]
        # Print the distance matrix after each intermediate vertex
        print(f'node {k+1} as intermediate node:\n', dist, '\n')

ماتریس مجاورت گراف شامل وزن‌های مسیرها بین راس‌ها است که در آن np.inf نشان‌دهنده نبود مسیر مستقیم بین دو راس است. این گراف همان ماتریس فاصله اولیه است که در توضیحات بالا با D₀ آن را نشان دادیم و به مرور آن را به‌روزرسانی کردیم.

نتیجه اجرای الگوریتم فلوید-وارشال را روی گرافی که در مثال بالا بررسی کردیم به شکل زیر می‌توان دید:

graph = np.array([
    [0, 5, np.inf, np.inf],
    [50, 0, 15, 5],
    [30, np.inf, 0, 15],
    [15, np.inf, 5, 0]
])

floyd_warshall(graph)

node1 as intermediate node:
[[ 0. 5. inf inf]
[50. 0. 15. 5.]
[30. 35. 0. 15.]
[15. 20. 5. 0.]]

node2 as intermediate node:
[[ 0. 5. 20. 10.]
[50. 0. 15. 5.]
[30. 35. 0. 15.]
[15. 20. 5. 0.]]

node3 as intermediate node:
[[ 0. 5. 20. 10.]
[45. 0. 15. 5.]
[30. 35. 0. 15.]
[15. 20. 5. 0.]]

node4 as intermediate node:
[[ 0. 5. 15. 10.]
[20. 0. 10. 5.]
[30. 35. 0. 15.]
[15. 20. 5. 0.]]

الگوریتم جانسون

الگوریتم جانسون (Johnson’s Algorithm) برای یافتن کوتاه‌ترین مسیر بین هر دو راس در گراف‌های بزرگ و پراکنده مناسب است. این الگوریتم ترکیبی از الگوریتم‌های بلمن-فورد و دایجسترا است و برای گراف‌هایی که شامل وزن‌های منفی هستند نیز کارایی دارد، به شرطی که دور منفی نداشته باشند.

تاریخچه الگوریتم جانسون

الگوریتم جانسون توسط دونالد بی. جانسون (Donald B. Johnson) در سال ۱۹۷۷ معرفی شد. جانسون این الگوریتم را به عنوان یک روش ترکیبی از الگوریتم دایجسترا و بلمن-فورد برای حل مسئله کوتاه‌ترین مسیر بین همه جفت‌های راس‌ها در گراف‌های بزرگ و پراکنده (Sparse graph) توسعه داد. الگوریتم جانسون به دلیل پیچیدگی زمانی بهینه‌تر و کارایی بالایش در گراف‌های بزرگ، به سرعت در جوامع علمی و صنعتی مورد توجه قرار گرفت.

الگوریتم جانسون چطور کار می‌کند؟

• برای اجرای الگوریتم جانسون ابتدا یک راس جدید به گراف اضافه می‌کنیم و یال‌هایی با وزن صفر از این راس جدید به تمام راس‌های موجود در گراف متصل می‌کنیم.
• سپس الگوریتم بلمن-فورد را از راس اضافه‌شده اجرا می‌کنیم تا کوتاه‌ترین فاصله از راس جدید به تمام راس‌های دیگر را به دست آوریم. اگر گراف دارای دور منفی باشد، الگوریتم بلمن-فورد در این مرحله آن را تشخیص می‌دهد و الگوریتم جانسون خاتمه می‌یابد.
• مقادیر به‌دست‌آمده از الگوریتم بلمن-فورد را به عنوان مقادیر پتانسیل (h) برای هر راس ذخیره می‌کنیم.
• در ادامه وزن‌ یال‌ها را با استفاده از مقادیر پتانسیل به‌دست‌آمده تنظیم می‌کنیم. وزن جدید (‘w) هر یال (u, v) با استفاده از فرمول زیر محاسبه می‌شود:

w'(u, v) = w(u, v) + h(u) - h(v)

• با این کار وزن‌ همه یال‌ها غیرمنفی می‌شود (شرطی که برای اجرای الگوریتم دایجسترا ضروری است).
• برای هر راس، الگوریتم دایجسترا را اجرا می‌کنیم تا کوتاه‌ترین مسیرها را در گراف با وزن‌های جدید پیدا کنیم.
• فاصله‌های به‌دست‌آمده را با استفاده از مقادیر پتانسیل به حالت اصلی برمی‌گردانیم. فاصله نهایی بین هر جفت راس (u, v) به صورت زیر محاسبه می‌شود:

d(u, v) = d'(u, v) + h(v) - h(u)

بررسی گام‌به‌گام مراحل اجرای الگوریتم جانسون

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

افزودن راس جدید

یک راس جدید به نام q اضافه می‌کنیم و آن را با وزن یال صفر به سایر راس‌ها متصل می‌کنیم:

اجرای الگوریتم بلمن-فورد

الگوریتم بلمن-فورد را از راس q روی گراف اجرا می‌کنیم تا فواصل کوتاه‌ترین مسیر را از راس q تا تمامی راس‌های گراف پیدا کنیم. خروجی این الگوریتم تابع پتانسیلh  را به ما می‌دهد که طبق فرمول گفته‌شده، برای وزن‌دهی مجدد یال‌ها استفاده می‌شود و تضمین می‌کند که وزن‌های گراف جدید مثبت باشند. به این ترتیب فاصله کوتاه‌ترین مسیرها از راس q تا همه راس‌های گراف ما یا همان مقادیر تابع پتانسیل h برای هر راس به صورت زیر خواهد بود:

h(A) = 0

h(B) = -5

h(C) = -3

h(D) = -4

وزن‌دهی مجدد یال‌ها

بر اساس فرمولی که در توضیحات الگوریتم جانسون ارائه کردیم، وزن جدید (‘w) هر یال (u, v) گراف با کمک تابع پتانسیل به‌صورت زیر محاسبه می‌شود:

w'(A, B) = w(A, B) + h(A) - h(B) \rightarrow w'(A, B) = -5 + 0 - (-5) = 0

w'(A, C) = w(A, C) + h(A) - h(C) \rightarrow w'(A, C) = 2 + 0 - (-3) = 5

w'(B, C) = w(B, C) + h(B) - h(C) \rightarrow w'(B, C) = 2 + (-5) - (-3) = 0

w'(B, D) = w(B, D) + h(B) - h(D) \rightarrow w'(B, D) = 1 + (-5) - (-4) = 0

w'(C, D) = w(C, D) + h(C) - h(D) \rightarrow w'(C, D) = 2 + (-3) - (-4) = 3

نهایتا وزن هر یال را با استفاده از اعدادی که بدست آوردیم تغییر می‌دهیم و راس q را از گراف حذف می‌کنیم. به این ترتیب گراف جدید به صورت زیر در می‌آید:

اجرای الگوریتم دایجسترا

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

d'(A, B) = 0

d'(A, C) = 0

d'(A, D) = 0

d'(B, A) = \infty

d'(B, C) = 0

d'(B, D) = 0

d'(C, A) = \infty

d'(C, B) = \infty

d'(C, D) = 3

d'(D, A) = \infty

d'(D, B) = \infty

d'(D, C) = \infty

در پایان فواصل محاسبه‌شده توسط الگوریتم دایجسترا را در گراف جدید، با استفاده از تابع پتانسیل به وزن‌های اصلی باز می‌گردانیم:

d(A, B) = d'(A, B) + h(B) - h(A) = 0 + (-5) - 0 = -5

d(A, C) = d'(A, C) + h(C) - h(A) = 0 + (-3) - 0 = -3

d(A, D) = d'(A, D) + h(D) - h(A) = 0 + (-4) - 0 = -4

d(B, A) = d'(B, A) + h(A) - h(B) = \infty + 0 - (-5) = \infty

d(B, C) = d'(B, C) + h(C) - h(B) = 0 + (-3) - (-5) = 2

d(B, D) = d'(B, D) + h(D) - h(B) = 0 + (-4) - (-5) = 1

d(C, A) = d'(C, A) + h(A) - h(C) = \infty + 0 - (-3) = \infty

d(C, B) = d'(C, B) + h(B) - h(C) = \infty + (-5) - (-3) = \infty

d(C, D) = d'(C, D) + h(D) - h(C) = 3 + (-4) - (-3) = 2

d(D, A) = d'(D, A) + h(A) - h(D) = \infty + 0 - (-4) = \infty

d(D, B) = d'(D, B) + h(B) - h(D) = \infty + (-5) - (-4) = \infty

d(D, C) = d'(D, C) + h(C) - h(D) = \infty + (-3) - (-4) = \infty

به این ترتیب، کوتاه‌ترین مسیرهای نهایی بین همه جفت راس‌ها در گراف اصلی به دست می‌آیند.

مرتبه زمانی الگوریتم جانسون

از آنجا که این الگوریتم از ترکیب الگوریتم‌های بلمن-فورد و دایجسترا استفاده می‌کند، مرتبه زمانی‌اش هم رابطه مستقیمی با مرتبه زمانی این دو الگوریتم دارد که در ادامه آن‌ها را بررسی می‌کنیم. برای یک گراف با V راس و E یال:

• افزودن راس جدید: اضافه کردن یک راس جدید به گراف و اتصال آن با وزن یال صفر به هر راس دیگر زمان O(V) را نیاز دارد.
• اجرای الگوریتم بلمن-فورد: جرای الگوریتم بلمن-فورد از راس جدید برای پیدا کردن فواصل کوتاه‌ترین مسیر به زمان O(V⋅E)  نیاز دارد.
• وزن‌گذاری مجدد یال‌ها: وزن‌های جدید برای هر یال با استفاده از تابع پتانسیل به زمان O(E) نیاز دارد.
• اجرای الگوریتم دایجسترا: اجرای الگوریتم دایجسترا از هر راس در گراف جدید با هیپ فیبوناچی به زمان O((V+E)logV) برای هر راس نیاز دارد. بنابراین برای تمام راس‌ها، این مرحله بهO(V⋅(V+E)logV)  زمان نیاز دارد.
• تنظیم فواصل نهایی: تبدیل فواصل محاسبه‌شده توسط الگوریتم دایجسترا به وزن‌های اصلی با استفاده از تابع پتانسیل به زمان O(V²) نیاز دارد.

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

O(V \cdot E + V^2 \log V)

پیاده‌سازی الگوریتم جانسون در پایتون

همان‌طور که گفته شد، برای محاسبه کوتاه‌ترین مسیر بین تمامی زوج راس‌ها در یک گراف وزن‌دار که ممکن است دارای وزن‌های منفی باشد، از ترکیبی از الگوریتم‌های بلمن-فورد و دایجسترا در قالب الگوریتم جانسون استفاده می‌کنیم:

تعریف تابع بلمن-فورد

برای این منظور ابتدا مانند قسمت‌های قبل، تابعی به نام bellman_ford تعریف می‌کنیم که فاصله‌ها از راس مبدا به سایر راس‌ها را محاسبه می‌کند:

def bellman_ford(graph, source):
    # Initialize distances from the source to all vertices as infinity
    # except the source itself which is set to zero
    dist = {vertex: float('infinity') for vertex in graph}
    dist[source] = 0

    # Define the order of vertices
    vertices = sorted(graph.keys())

    # Relax edges repeatedly
    for _ in range(len(graph) - 1):
        for vertex in graph:
            for neighbor, weight in graph[vertex].items():
                if dist[vertex] + weight < dist[neighbor]:
                    dist[neighbor] = dist[vertex] + weight

    # Check for negative weight cycles
    for vertex in graph:
        for neighbor, weight in graph[vertex].items():
            if dist[vertex] + weight < dist[neighbor]:
                print("Graph contains a negative weight cycle")

    return dist

تعریف تابع دایجسترا

سپس، تابع dijkstra را برای محاسبه کوتاه‌ترین مسیر از یک راس به سایر راس‌ها در گراف وزن‌دار (بدون وزن منفی) تعریف می‌کنیم:

def dijkstra(graph, source):
    # Initialize distances from the source to all vertices as infinity
    dist = {vertex: float('infinity') for vertex in graph}
    dist[source] = 0
    # Set to keep track of vertices included in the shortest path tree
    sptSet = set()

    while len(sptSet) < len(graph):
        # Select the vertex with the minimum distance value
        u = min((vertex for vertex in dist if vertex not in sptSet), key=dist.get)
        # Add the selected vertex to the set
        sptSet.add(u)

        for neighbor, weight in graph[u].items():
            if neighbor not in sptSet:
                if dist[u] + weight < dist[neighbor]:
                    dist[neighbor] = dist[u] + weight

    return dist

تعریف تابع جانسون

در نهایت، تابع johnson را که از دو تابع bellman_ford و dijkstra استفاده می‌کند، تعریف می‌کنیم. در این تابع ابتدا یک راس جدید (new_vertex) به نام q به گراف اضافه می‌شود با یالی با وزن صفر به همه رئوس گراف وصل می‌شود (v: 0 for v in graph). سپس تابع bellman_ford روی گراف، با راس شروع q اجرا می‌شود. سپس یک گراف جدید به نام reweighted_graph ایجاد می‌کنیم که در آن برای هر راس u در گراف اصلی، وزن جدید یالی که از راس u به هر راس همسایه می‌رود را در خود ذخیره می‌کند. همان‌طور که در توضیح الگوریتم جانسون گفتیم، وزن‌های جدید بر اساس فرمول w + h[u] - h[v] محاسبه می‌شوند که در آن:

• w وزن اصلی یال بین u و v در گراف اصلی است.
• h[u] کوتاه‌ترین مسیر رسیدن به راس u از راس مبدا q (با استفاده از الگوریتم بلمن-فورد) است.
• h[v] کوتاه‌ترین مسیر رسیدن به راس v (یکی از همسایه‌های راس u در گراف اصلی) از راس مبدا q (با استفاده از الگوریتم بلمن-فورد) است.

def johnson(graph):
    # Add a new vertex 'q' with zero-weight edges to all other vertices
    new_vertex = 'q'
    new_graph = {new_vertex: {v: 0 for v in graph}}
    new_graph.update(graph)

    # Run Bellman-Ford with 'q' as source node
    h = bellman_ford(new_graph, new_vertex)
    # Reweight the edges
    reweighted_graph = {u : {v: w + h[u] - h[v] for v, w in edges.items()} for u, edges in graph.items()}

در ادامه یک دیکشنری خالی به نام all_pairs_shortest_paths ایجاد می‌کنیم که در نهایت شامل کوتاه‌ترین مسیرها برای تمامی زوج راس‌ها خواهد بود. کلیدهای (keys) این دیکشنری راس‌های گراف و مقادیر (values) آن‌ها دیکشنری‌های دیگری هستند که نشان‌دهنده کوتاه‌ترین مسیرها از هر راس به همه دیگر راس‌ها است.

سپس، تابع dijkstra را به تعداد رئوس گراف اصلی و هر بار با یک راس شروع متفاوت (u)، روی گراف جدید یا همان reweighted_graph فراخوانی می‌کنیم. همان‌طور که در بخش پیاده‌سازی الگوریتم دایجسترا دیدید، خروجی این تابع در هر بار، یک دیکشنری است که کوتاه‌ترین فاصله از راس مبدا به هر یک از رئوس دیگر را به ما می‌دهد.

نهایتا با کمک خروجی الگوریتم دایجسترا، دیکشنری all_pairs_shortest_paths را برای هر راس بر اساس فرمول d + h[v] - h[v] محاسبه می‌کنیم. که در آن:

• u راسی است که برای اجرای الگوریتم دایجسترا روی گراف جدید به عنوان راس مبدا در نظر گرفته شده است.
• v راسی است که فاصله کوتاه‌ترین مسیر از راس u تا آن با کمک دایجسترا روی گراف جدید محاسبه شده است.
• d فاصله کوتاه‌ترین مسیر از راس مبدا u به v در گراف جدید است.
• h[v] کوتاه‌ترین مسیر رسیدن به راس v از راس مبدا u (با استفاده از الگوریتم دایجسترا) است.

    # Run Dijkstra's algorithm for each vertex
    all_pairs_shortest_paths = {}
    for u in graph:
        dist = dijkstra(reweighted_graph, u)
        all_pairs_shortest_paths[u] = {v: d + h[v] - h[u] for v, d in dist.items()}
        print(f'{u} as source', ': ', all_pairs_shortest_paths,'\n')

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

graph = {
    'A': {'B': -5, 'C': 2},
    'B': {'C': 2, 'D': 1},
    'C': {'D': 2},
    'D': {}
}

johnson(graph)

A as source:
{‘A’: {‘A’: 0, ‘B’: -5, ‘C’: -3, ‘D’: -4}}
B as source:
{‘A’: {‘A’: 0, ‘B’: -5, ‘C’: -3, ‘D’: -4}, ‘B’: {‘A’: inf, ‘B’: 0, ‘C’: 2, ‘D’: 1}}
C as source:
{‘A’: {‘A’: 0, ‘B’: -5, ‘C’: -3, ‘D’: -4}, ‘B’: {‘A’: inf, ‘B’: 0, ‘C’: 2, ‘D’: 1}, ‘C’: {‘A’: inf, ‘B’: inf, ‘C’: 0, ‘D’: 2}}
D as source:
{‘A’: {‘A’: 0, ‘B’: -5, ‘C’: -3, ‘D’: -4}, ‘B’: {‘A’: inf, ‘B’: 0, ‘C’: 2, ‘D’: 1}, ‘C’: {‘A’: inf, ‘B’: inf, ‘C’: 0, ‘D’: 2}, ‘D’: {‘A’: inf, ‘B’: inf, ‘C’: inf, ‘D’: 0}}

یافتن کوتاه‌ترین مسیر بین هر دو راس در گراف بدون وزن

در گراف‌های بدون وزن، یافتن کوتاه‌ترین مسیر بین هر دو راس می‌تواند با استفاده از الگوریتم‌های ساده‌تری انجام شود. برای یافتن کوتاه‌ترین مسیر بین هر دو راس در گراف بدون وزن هم می‌توان از الگوریتم جستجوی سطح اول (BFS) استفاده کرد. این الگوریتم با استفاده از صف، به ترتیب تمام راس‌های همسایه را بازدید می‌کند و کوتاه‌ترین مسیرها را بین جفت راس‌ها محاسبه می‌کند.

همه کوتاه‌ترین مسیرها در یک گراف بی‌وزن را چطور می‌توان بدست آورد؟

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

برای این منظور به صورت زیر عمل می‌کنیم:

• ابتدا یک ماتریس به ابعاد n×n ایجاد می‌کنیم، که n تعداد راس‌های گراف است.
• سپس تمامی مقادیر این ماتریس را به مقدار بی‌نهایت تنظیم می‌کنیم، بجز قطر اصلی که مقدار آن صفر است (فاصله هر راس با خودش).
• حال برای هر راس در گراف به عنوان راس مبدا، الگوریتم BFS را اجرا می‌کنیم.
• یک صف خالی و یک آرایه برای نگهداری فاصله‌ی هر گره از مبدا ایجاد می‌کنیم.
• راس مبدا را به صف اضافه و فاصله آن را از خودش صفر قرار می‌دهیم.
• تا زمانی که صف خالی نشده:
  • گره اول صف را از صف خارج می‌کنیم.
  • تمامی همسایه‌های گره‌ی خارج شده را بررسی می‌کنیم. اگر این همسایه‌ها هنوز بازدید نشده باشند، به صف اضافه می‌شوند و فاصله‌ی آن‌ها از راس مبدا برابر با فاصله‌ی گره‌ی فعلی به اضافه‌ی یک تنظیم می‌شود.
• نتایج اجرای BFS برای هر راس را در ماتریس n×n  ذخیره می‌کنیم.

در نهایت، این ماتریس به ما نشان می‌دهد که کوتاه‌ترین فاصله بین تمامی جفت‌ راس‌ها چقدر است.

مرتبه زمانی الگوریتم جستجوی سطح اول برای پیدا کردن همه کوتاه‌ترین مسیرها در گراف بی‌وزن

هر بار اجرای الگوریتم BFS دارای پیچیدگی زمانی O(V+E) است. با توجه به این که الگوریتم BFS را برای هر یک از V راس اجرا می‌کنیم، پیچیدگی زمانی کل الگوریتم به صورت زیر خواهد بود:

O(V^2 + V \cdot E)

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

پیاده‌سازی الگوریتم جستجوی سطح اول برای همه کوتاه‌ترین مسیرها در پایتون

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

تابع bfs_shortest_paths

در این تابع از الگوریتم BFS برای یافتن کوتاه‌ترین مسیرها از یک راس مبدا به سایر راس‌ها در یک گراف بدون وزن استفاده می‌کنیم. برای این منظور دیکشنری distances ایجاد می‌کنیم که فاصله هر راس از راس مبدا را نگه می‌دارد. ابتدا تمامی مقادیر این دیکشنری را به مقدار بی‌نهایت تنظیم می‌کنیم و بعد فاصله راس مبدا از خودش برابر با صفر قرار می‌دهیم. در ادامه یک صف (queue) از راس‌های در حال پردازش ایجاد و راس مبدا را به صف اضافه می‌کنیم. تا زمانی که صف خالی نشده است، گره اول صف از صف خارج و تمامی همسایه‌های گره خارج شده بررسی می‌کنیم. اگر فاصله همسایه برابر با بی‌نهایت باشد، این همسایه را به صف اضافه کرده و فاصله آن از راس مبدا برابر با فاصله گره فعلی به اضافه یک تنظیم می‌کنیم. در نهایت، دیکشنری distances که فاصله‌های کوتاه‌ترین مسیر از راس مبدا به سایر راس‌ها را نگه می‌دارد، باز می‌گردانیم:

from collections import deque

def bfs_shortest_paths(graph, start):
    # Initialize distances to all vertices as infinity
    distances = {vertex: float('infinity') for vertex in graph}
    # Distance to the start vertex is set to 0
    distances[start] = 0
    # Initialize the queue with the start vertex
    queue = deque([start])

    # Process the queue until it is empty
    while queue:
        node = queue.popleft()
        # Iterate through neighbors of the current node
        for neighbor in graph[node]:
            # If the neighbor has not been visited, update the distance
            if distances[neighbor] == float('infinity'):
                queue.append(neighbor)
                distances[neighbor] = distances[node] + 1
    return distances

تابع  all_pairs_shortest_paths

این تابع برای یافتن کوتاه‌ترین مسیرها بین تمامی جفت‌های راس‌ها در یک گراف بدون وزن استفاده می‌شود. در این تابع، ابتدا یک دیکشنری به نام all_distances ایجاد می‌کنیم که فاصله‌های کوتاه‌ترین مسیر بین تمامی جفت‌های راس‌ها را نگه می‌دارد. برای هر راس در گراف، تابع bfs_shortest_paths را فراخوانی می‌کنیم تا فاصله‌های کوتاه‌ترین مسیر از آن راس به سایر راس‌ها محاسبه شود. نتایج هر فراخوانی را در دیکشنری all_distances ذخیره کرده و پس از فراخوانی هر راس، محتویات دیکشنری را چاپ می‌کنیم:

def all_pairs_shortest_paths(graph):
    # Initialize a dictionary to store distances for all pairs
    all_distances = {}
    # Calculate shortest paths for each vertex
    for vertex in graph:
        all_distances[vertex] = bfs_shortest_paths(graph, vertex)
        print(all_distances)

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

graph = {
    'A': ['B', 'C', 'D'],
    'B': ['A', 'D'],
    'C': ['A', 'E'],
    'D': ['A', 'B'],
    'E': ['C', 'F'],
    'F': ['E']
}

all_pairs_shortest_paths(graph)

{‘A’: {‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: 1, ‘E’: 2}}

{‘A’: {‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: 1, ‘E’: 2}, ‘B’: {‘A’: 1, ‘B’: 0, ‘C’: 2, ‘D’: 1, ‘E’: 3}}

{‘A’: {‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: 1, ‘E’: 2}, ‘B’: {‘A’: 1, ‘B’: 0, ‘C’: 2, ‘D’: 1, ‘E’: 3}, ‘C’: {‘A’: 1, ‘B’: 2, ‘C’: 0, ‘D’: 2, ‘E’: 1}}

{‘A’: {‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: 1, ‘E’: 2}, ‘B’: {‘A’: 1, ‘B’: 0, ‘C’: 2, ‘D’: 1, ‘E’: 3}, ‘C’: {‘A’: 1, ‘B’: 2, ‘C’: 0, ‘D’: 2, ‘E’: 1}, ‘D’: {‘A’: 1, ‘B’: 1, ‘C’: 2, ‘D’: 0, ‘E’: 3}}

{‘A’: {‘A’: 0, ‘B’: 1, ‘C’: 1, ‘D’: 1, ‘E’: 2}, ‘B’: {‘A’: 1, ‘B’: 0, ‘C’: 2, ‘D’: 1, ‘E’: 3}, ‘C’: {‘A’: 1, ‘B’: 2, ‘C’: 0, ‘D’: 2, ‘E’: 1}, ‘D’: {‘A’: 1, ‘B’: 1, ‘C’: 2, ‘D’: 0, ‘E’: 3}, ‘E’: {‘A’: 2, ‘B’: 3, ‘C’: 1, ‘D’: 3, ‘E’: 0}}

مجموعه کامل کدهای استفاده شده در این مطلب، از گیت‌هاب ریپوزیتوری Shortest Path Problem قابل دسترسی است.

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

نام الگوریتم	بهترین پیچیدگی زمانی	دسته‌بندی	توضیحات
دایجسترا	O(E + VlogV)	یک راس تا سایر رئوس	الگوریتم حریصانه برای یافتن کوتاه‌ترین مسیر از یک راس مبدا به سایر راس‌ها در یک گراف وزن‌دار.
بلمن-فورد	O(V.E)	یک راس تا سایر رئوس	الگوریتمی برای مدیریت گراف‌های با وزن منفی و تشخیص دورهای منفی.
فلوید-وارشال	O(V3)	همه جفت راس‌ها	الگوریتم برنامه‌نویسی پویا برای یافتن کوتاه‌ترین مسیر بین تمامی جفت‌های راس‌ها در یک گراف وزن‌دار.
جانسون	O(V.E+V2logV)	همه جفت راس‌ها	ترکیبی از الگوریتم‌های بلمن-فورد و دایجسترا، مناسب برای گراف‌های بزرگ و پراکنده با وزن‌های منفی.
جستجوی سطح اول (BFS)	O(V+E)	یک راس تا سایر رئوس	الگوریتم ساده برای پیمایش گراف و یافتن کوتاه‌ترین مسیر در گراف‌های بدون وزن.
کوتاه‌ترین مسیر در DAG	O(V+E)	یک راس تا سایر رئوس	الگوریتم خاص برای یافتن کوتاه‌ترین مسیر در گراف‌های جهت‌دار بدون دور (DAG) با استفاده از مرتب‌سازی توپولوژیکی.
جستجوی سطح اول (BFS)	O(V2+V.E)	همه جفت راس‌ها	الگوریتم برای یافتن کوتاه‌ترین مسیر بین تمامی جفت‌های راس‌ها در یک گراف بدون وزن.

کلام آخر درباره الگوریتم‌های کوتاه‌ترین مسیر در گراف

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

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

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

پرسش‌های متداول

الگوریتم دایجسترا چیست و چگونه کوتاه‌ترین مسیر در گراف را پیدا می‌کند؟

الگوریتم دایجسترا (Dijkstra’s Algorithm) یک الگوریتم حریصانه (Greedy Algorithm) است که برای یافتن کوتاه‌ترین مسیر از یک راس مبدا به سایر راس‌ها در یک گراف وزن‌دار (Weighted Graph) استفاده می‌شود. این الگوریتم با انتخاب مسیر با کمترین هزینه در هر مرحله، به تدریج کوتاه‌ترین مسیرها را محاسبه می‌کند.

الگوریتم بلمن-فورد چگونه با وزن‌های منفی مقابله می‌کند؟

الگوریتم بلمن-فورد (Bellman-Ford Algorithm) قادر به مدیریت یال‌های با وزن منفی است و می‌تواند دورهای منفی (Negative Cycles) را شناسایی کند. این الگوریتم با چندین بار عبور از روی تمامی یال‌ها، فاصله‌های کوتاه‌ترین مسیر را به‌روزرسانی می‌کند و در نهایت اگر تغییری در فاصله‌ها مشاهده شود، نشان‌دهنده وجود دور منفی در گراف است.

الگوریتم فلوید-وارشال چه کاربردهایی دارد و چگونه کوتاه‌ترین مسیر در گراف را پیدا می‌کند؟

الگوریتم فلوید-وارشال (Floyd-Warshall Algorithm) برای یافتن کوتاه‌ترین مسیر بین تمامی جفت‌های راس‌ها در یک گراف وزن‌دار استفاده می‌شود. این الگوریتم با استفاده از رویکرد برنامه‌نویسی پویا (Dynamic Programming) یک ماتریس فاصله ایجاد می‌کند و به تدریج با استفاده از تمامی راس‌ها به عنوان راس واسطه، این ماتریس را به‌روزرسانی می‌کند.

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

الگوریتم جانسون (Johnson’s Algorithm) ترکیبی از الگوریتم‌های بلمن-فورد و دایجسترا است و برای گراف‌های بزرگ و پراکنده (Sparse Graphs) با وزن‌های منفی مناسب است. این الگوریتم با اضافه کردن یک راس جدید به گراف و تنظیم وزن‌های یال‌ها، همه یال‌ها را غیرمنفی می‌کند و سپس با استفاده از الگوریتم دایجسترا کوتاه‌ترین مسیرها را محاسبه می‌کند.

چه تفاوت‌هایی بین گراف وزن‌دار و بدون وزن وجود دارد و چگونه الگوریتم‌های مختلف برای پیدا کردن کوتاه‌ترین مسیر در آن‌ها عمل می‌کنند؟

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

یادگیری تحلیل داده را از امروز شروع کنید!

دنیای داده‌ها جذاب است و دانستن علم داده، توانایی تحلیل داده‌، یا بازاریابی مبتنی بر داده، شما را برای فرصت‌های شغلی بسیاری مناسب می‌کند. فارغ از رشته‌ و پیش‌زمینه‌، می‌توانید حالا شروع کنید و از سطح مقدماتی تا پیشرفته بیاموزید. اگر دوست دارید به این حوزه وارد شوید، پیشنهاد می‌کنیم با کلیک روی این لینک قدم اول را همین حالا بردارید.

مشاوران کافه‌تدریس به شما کمک می‌کنند مسیر یادگیری برای ورود به این حوزه را شروع کنید:

دوره جامع دیتا ساینس و ماشین لرنینگ