Некоторые преимущества использования кучи или контейнера set в STL для реализации алгоритма Дейкстры:

• Оптимизированный поиск. 1 Если хранить все неокрашенные вершины в куче или в контейнере set (реализованном при помощи сбалансированного дерева поиска), то поиск очередной вершины для окрашивания можно производить более оптимально. 1
• Более высокая производительность на разреженных графах. 1 В этом случае алгоритм Дейкстры с использованием кучи работает существенно быстрее, чем обычный алгоритм Дейкстры. 1
• Эффективное извлечение узла с наименьшим предварительным расстоянием. 3 Упорядоченный набор для отслеживания необработанных узлов позволяет эффективно извлекать минимальный элемент. 3

Однако у такого подхода есть и недостатки: обновление расстояния до другой вершины выполняется за O(log n), так как это требует перестройки кучи или дерева поиска. 1 Кроме того, на плотных графах (если m ∼ n^2) алгоритм Дейкстры с использованием кучи, наоборот, менее эффективен, чем простая реализация Дейкстры. 1