tgoop.com/the_algorithms/4624
Last Update:
Кратчайший путь с одним источником в направленных ациклических графах
Задача нахождения кратчайшего пути от одной вершины ко всем остальным вершинам в графе.
Алгоритм:
1. Инициализируйте расстояния от источника до всех остальных вершин графа бесконечно большими значениями, кроме расстояния от источника до самого себя, которое равно нулю.
2. Создайте очередь с приоритетом, в которой будут храниться вершины, и положите в нее источник.
3. Пока очередь с приоритетом не пуста извлеките вершину из очереди с приоритетом, установите ее как текущую вершину и пройдитесь по всем смежным вершинам текущей вершины:
⁃ Если новое расстояние (расстояние от источника до текущей вершины + вес ребра до смежной вершины) меньше текущего расстояния до смежной вершины, обновите расстояние.
⁃ Если смежная вершина еще не была посещена, добавьте ее в очередь с приоритетом.
4. Верните расстояния от источника до всех остальных вершин.
Сложность: O((V + E) log V)
BY Алгоритмы и структуры данных
Share with your friend now:
tgoop.com/the_algorithms/4624