الگوریتم های bellmand-ford و dijekstra

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

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

الگوریتم دایکسترا یکی از الگوریتم‌های مورد استفاده برای محاسبه کوتاه ترین مسیر تک منبع (single-source shortest path) هستش و مشابه الگوریتم پریم هستش. در صورتی که گراف یال با وزن منفی داشته باشه، این الگوریتم درست کار نمی‌کنه و می‌بایست از الگوریتم‌های دیگر نظیر الگوریتم بلمن-فورد که پیچیدگی زمانی آنها بیشتره استفاده کنیم.

توضیحات بیشتر در لینک زیر :

دایکسترا

بلمن-فورد