Это хорошо известный алгоритм, используемый для поиска кратчайшего расстояния и кратчайшего пути от одного исходного узла до всех других узлов в графе. Этот алгоритм работает только с графами, в которых нет отрицательных циклов (т.е. цикл, сумма ребер которого равна отрицательному значению).
Алгоритм
- Создайте набор «замеченных», чтобы отслеживать посещенные узлы.
- Создайте словарь «parentMap» для карты родителей, чтобы восстановить путь после выполнения алгоритма.
- Создайте словарь «nodeCosts» для отслеживания минимальных затрат на достижение различных узлов от исходного узла и инициализируйте стоимость для исходного узла равной 0.
- Создайте структуру данных очереди приоритетов (в Python используйте модуль heapq со списком) и вставьте кортеж (0, исходный узел) в очередь приоритетов (куча), представляющая (стоимость узла от исходного узла, самого узла).
- внутри цикла while, пока в очереди с приоритетами ничего не останется. во время цикла вытолкните узел с минимальными затратами.
- перебрать все соседние узлы всплывающего узла. если они не были исследованы ранее и их общая стоимость меньше, чем стоимость в «nodeCosts», добавьте их также в очередь приоритетов и обновите «parentMap».
- Восстановите путь из «parentMap».
Код
Реконструкция пути с помощью parentMap тривиальна.
Дополнительно
- Если нам просто нужен кратчайший путь от некоторого исходного узла к другому узлу, скажем, «конечному узлу», мы можем досрочно выйти из цикла while (когда мы извлекаем узлы с минимальной стоимостью из кучи, и этот узел оказывается концом узел).
- Вышеупомянутая реализация представляет собой ленивую реализацию алгоритма Дейкстры (мы добавляем узлы в кучу, но в этой куче может быть тот же узел с более высокой стоимостью, который поступает по другому пути), также есть энергичная реализация, которую можно найти в моем GitHub.
Если вы обнаружили какую-либо ошибку где-либо в блоге или хотите предложить что-то добавить к ней, подумайте о том, чтобы прокомментировать то же самое.
Спасибо за прочтение.
