Алгоритм Дейкстры (Dijkstra's algorithm)
Алгоритм Дейкстры предназначен для поиска пути с наименьшим суммарным весом во взвешенном графе.
Алгоритм основан на последовательном «взвешивании» узлов графа. На первой итерации вес начального узла принимается за 0, вес конечного узла за бесконечность, а вес остальных узлов неизвестен. Все узлы считаются необработанными.
Пока остаются необработанные узлы
Найти узел с наименьшей стоимостью
Обновить стоимость соседей узла
Если были обновления то обновить таблицу с родителями
Пометить узел как пройденный
Вычислить итоговый путь
Алгоритм Дейкстры работает только на направленных ациклических графах. Алгоритм Дейкстры не работает с взвешенными графами с отрицательным весом, для таких графов применяется алгоритм Беллмана-Форда.
Ссылки
- [BhargavaGrokaemAlgoritmy2018 090]