Является ли c ++ std :: priority_queue правильной структурой для очереди dijkstra?
Я не думаю, что очередь приоритетов c ++ является правильной структурой для очереди dijkstra, потому что она не содержит функциональных возможностей для простого поиска или удаления элементов.
Правильная структура — это куча Фибоначчи, но в библиотеке std ее нет.
У кого-нибудь есть предложения по лучшей, реализованной на c ++ структуре?
Решение
Ты можешь использовать std::set и хранить пару<расстояние, вершина> в этом. Для поиска и удаления элементов вы можете сохранить расстояние до каждой вершины в массиве или в std::vector получить пару<расстояние, вершина> для данной вершины быстро. Ближайшая не посещенная вершина всегда находится в первом элементе множества (и может быть получена с помощью set.begin()).
Другие решения
Для большинства практических целей std::priority_queue основанная реализация достаточно хороша для разреженных графов. Реализация Dijkstra таким образом имеет время выполнения O(E log V), Если у вас достаточно плотный график, вы можете просто использовать основные O(V*V) версия алгоритма Дейкстры. Поскольку граф становится более плотным, асимптотика версии Fib-heap приближается к ванильной реализации.