گروه کامپیوتر

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

در نظریه گراف، الگوریتم دیکسترا (به انگلیسیDijkstra’s algorithm) یکی از الگوریتم‌های پیمایش گراف است که توسط دانشمند هلندیعلوم رایانه، اِدْسْخِر دیْکْسْترا در سال ۱۹۵۹ ارائه شد.

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