Motivation

Алгоритм Дейкстры расширяет множество вершин, кратчайшее расстояние до которых уже известно. Он всегда фиксирует ближайшую еще не зафиксированную вершину, а затем использует ее для улучшения (релаксации) расстояний до ее соседей.

Зачем изучать алгоритм Дейкстры?

• Повсеместное использование: GPS-маршрутизация, маршрутизация сетевых пакетов и любой поиск пути с минимальной стоимостью.
• Работающий жадный алгоритм: чистый пример жадного выбора, который доказуемо дает оптимальный результат, пока веса ребер не являются отрицательными.
• Фундамент: идея релаксации используется в A* и других алгоритмах поиска кратчайшего пути.

Важно: Алгоритм Дейкстры предполагает отсутствие отрицательных весов. Для ребер с отрицательным весом требуется алгоритм Беллмана-Форда, который рассматривается в следующем курсе.