قراره در این پست به بررسی مسئله کلاسیک کوتاه ترین مسیر در گراف بپردازیم که برای افرادی که توی زمینه علوم کامپیوتر تازه کار تر هستند می تونه خیلی مفید باشه :) 

و قراره که چند نفری رو دعوت کنم که از این پست استفاده کنند.


این مسئله صورت های مختلفی دارد که با آشنایی با الگوریتم ها با صورت های مختلف آن هم آشنا خواهیم شد.
اما مسئله در حالت کلی به این صورت است که معمولا با یک گراف سرو کار داریم و هدف یافتن کوتاهترین مسیر (دنباله ای از رئوس گراف) بین دو راس می باشد... حال بسیاری از مسائل را می توان پس از مدل کردنشان به یک گراف با استفاده از این الگوریتم ها حل کرد. :)

الگوریتم Dijkstra
این الگوریتم مسئله را برای گراف های وزن دار حل می کند.
الگوریتم از یک راس (ریشه) شروع می شود و بعد از اتمام کوتاه ترین فاصله هر راس تا راس ریشه را در یک آرایه ذخیره می کند و در واقع یک درخت می سازد که در این درخت مسیر یکتای هر راس تا ریشه کوتاه ترین فاصله آن راس تا ریشه در گراف اصلی است فاصله هر راس را ریشه را در یک آرایه نگه می داریم که در ابتدا همه ی مقادی مقدار بینهایت می دهیم. (یک عدد خیلی بزرگ که مطمئنیم از بلندترین مسیرمان هم بیشتر است)
ایده حل نسبتا ساده و سرراست است فرض کنید تا این جای کار الگوریتم یک درخت ساخته است و هر یک از راس های این درخت یک کوتاه ترین مسیر تا ریشه دارند (فاصله) بین تمام راس هایی که به راس های این درخت وصل هستند و هنوز در درخت نیستند آن راسی را انتخاب می کنیم که اگر با یک یال به یکی از راس های درخت وصل شود از بقیه کوتاه تر باشد (مجموع وزن یال و فاصله راس داخل درخت که به آن وصل شده است تا ریشه کمینه شود) بدیهی است که چرا این روش گریدی جواب می دهد فرض کنید راسی که کمترین فاصله را تا ریشه با این روش دارد را v بنامیم اگر قرار باشد با مسیری غیر این یال اضافه شده راس v را به درخت اضافه کنیم قطعا فاصله نهایی راس v از فاصله ای که به دست آورده ایم بهتر نخواهد شد زیرا اولین راسی که به جای v‌ اضافه شده فاصله ای بیشتر مساوی تا ریشه نسبت به راس v با یال اضافه شده توسط دایکسترا دارد و در ابتدا هم که درختمان تنها یک راس ریشه را دارد.
توضیحات بیشتر را در ویکی پدیا ببینید.
پیچیدگی : اگر n راس و m‌ یال داشته باشیم و گراف همبند باشد (m>=n-1) می توان پیاده سازی را به شکلی انجام داد که n-1‌ مرحله راس اضافه کردن به درخت دایکسترا داشته باشیم و در هر مرحله راس بهینه برای اضافه کردن به درخت را با log n به دست بیاوریم اگر از درخت دودویی جستجو یا هرم استفاده کنیم می توان الگوریتم را در (O(mlogn حل کرد. که البته با استفاده از هرم فیبوناچی در زمان کمتر هم قابل حله. (این کار زیاد کاربردی نیست! :) )
برای این کار در هر مرحله تمام راس هایی که یک همسایه در درخت مفروض دایکسترا دارند را به محدوده جستجو اضافه می کنیم (درخت دودویی جستجو یا هرم) این اضافه کردن زمانی انجام می شود که همسایه آن به درخت دایکسترا اضافه شده باشد. و هر راس را به صورت یک زوج مرتب (pair در c++) به درخت اضافه می کنیم که عضو اول فاصله آن راس تا ریشه است که برابر است با فاصله همسایه اش (می توان پدر این راس نامید زیرا درختمان ریشه دار است) که باعث افزوده شدن این راس به درخت شده است به علاوه وزن یال بین این دو راس اگر بعد افزودن این راس به درخت قبلا با یک فاصله دیگری در محدوده جستجو وجود داشت و فاصله تولید شده فعلی از فاصله قبلی کمتر بود با log n آن را از محدوده حذف کرده چک کردن با (o(1 انجام می شود (در آرایه فاصله برای هر راسی که در محدوده جستجو است، فاصله ای که با آن در محدوده جستجو قرار دارد و تا به اینجا بهینه است را ذخیره می کنیم) و با فاصله جدید به محدوده با log n اضافه اش می کنم پس هر یال حداکثر یک بار وارد محدوده شده و یک بار خارج می شود.
این سوال می تواند تمرین خوبی برای فهم بیشتر این الگوریتم باشد.

الگوریتم BFS
این الگوریتم مسئله را برای گراف های بدون وزن حل می کند.
در واقع این الگوریتم حال خاص الگوریتم دایکسترا است که همه ی یال ها وزن برابر با یک دارند. و در هر مرحله به جای جستجو در یک درخت دودویی جستجو یا یک هرم می توان قدیمی ترین راسی را اضافه کرد که به محدوده جستجو وارد شده است با کمی بررسی می توانید به راحتی ببینید که این راس در واقع همان راس بهینه در الگوریتم دایکسترا است پس برای این کار از یک صف استفاده می کنیم و راس بهینه را با (O(1 به درخت اضافه می کنیم. پس پیچیدگی آن برابر با (O(E خواهد بود. :)

در هر دو الگوریتم قبلی می توان با روش های مختلف درخت نهایی مسئله را هم ذخیره کرد. و کوتاهترین مسیر بین دو راس را نمایش داد.

الگوریتم Floyed Warshall
این الگوریتم یک الگوریتم داینامیک هست که بعد از اجرا با زمان (O(n^3 کوتاهترین فاصله بین هر دو راس را در یک ماتریس نگه می دارد.
خوبی این الگوریتم این است که کوتاهترین فاصله بین هر دوراس را داریم و بدی آن زمان اجرای بالای آن است.
این فایل خیلی خوب توضیحش داده
در پیاده سازی بالا یک ماتریس دیگر تعریف شده است و آخرین راسی که به وسیله آن فاصله ی بین راس های u و v آپدیت شده است نگه داشته شده است و به وسیله این ماتریس و یک الگوریتم بازگشتی می توان مسیر بین دو راس u‌و v را هم چاپ کرد.
این هم یک سوال نسبتا ساده برای تمرین پیاده سازی این الگوریتم

الگوریتم ‌Bellman Ford
این الگوریتم برای گراف هایی که دور منفی دارند کوتاهترین فاصله برای هر راس از ریشه را به دست می آورد و اگر دور منفی وجود داشته باشد وجود آن را اعلام می کند (اگر در یک گراف دور منفی وجود داشته باشد می توانیم توی آن دور هر چه قدر که می خواهیم دور بزنیم و فاصله بین دو راس را پس از هر دور منفی تر کنیم :D ) چرا که وجود دور منفی مسئله را بی معنی می کند.
توضیحات بیشتر را در ویکی پدیا ببینید که نسبتا خوب توضیحش داده
پیچیدگی : پیچیدگی این الگوریتم از (O(nm است اگر n‌ تعداد راس ها و m‌ تعداد یال ها باشد.
این هم یک تمرین خوب برای فهم بیشتر این الگوریتم