الگوریتم های گراف

به نام خدا

سلام و درود .
در این پست قصد داریم یکی از مسائل مهم توی گراف و الگوریتم های گراف به نام « کوتاه ترین مسیر » را بررسی کنیم.
لطفا برای مطالعه ی بیشتر به ادامه مطلب مراجعه نمایید.


همان طور که گفته شد قرار است الگوریتم های کوتاه ترین مسیر را در یک گراف تشریح کنیم.

کتاب « clrs » این بحث را به دو قسمت تقسیم کرده است :
 ۱-الگوریتم کوتاه ترین مسیر ها از مبدا واحد

 ۲-الگوریتم کوتاه ترین مسیر ها از هر راس به راس دیگر


"کوتاه ترین مسیر ها از مبدا واحد " :
اولین الگوریتمی که بررسی خواهیم کرد ، الگوریتم « دایکسترا » نام دارد.

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

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

به نظر من بهترین راه برای یادگیری این الگوریتم ، بهره گیری از شکل زیر است :

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

بقیه الگوریتم هارو توی پست های بعدی بررسی خواهیم کرد.