Когда мне нужно реализовать алгоритм Дейкстры, я обычно делаю это, используя двоичную кучу без операции уменьшения_ключа.
Для этого вы помещаете записи (стоимость, вершина) в кучу, и всякий раз, когда стоимость вершины уменьшается, вы просто добавляете новую. Когда вы вытаскиваете вершину из кучи, просто игнорируйте ее, если она уже сделана. В любом случае вы должны следить за тем, какие вершины создаются. Это просто.
Это занимает немного больше места, но сложность остается O (| E | log V) (что совпадает с O (| V + E | log | V |) или O (| E | log | E | ) для подключенного компонента, который будет проходить алгоритм)
Теперь коэффициент log | E | Вышеизложенное вытекает из того факта, что существует до | E | элементы в куче. Если вы сгруппируете все элементы с одинаковым приоритетом в списки и поместите эти списки в очередь с приоритетами, то журнал | E | коэффициент превращается в лог (количество различных приоритетов). Обратите внимание, что массив кучи перестает быть подходящей структурой для очереди приоритетов, но различные виды упорядоченных деревьев работают нормально. Это легко, когда вам не нужен ключ_памяти.
В вашем случае разница в стоимости между вершинами в начале приоритетной очереди и самой высокой стоимостью в приоритетной очереди составляет не более 2 ^ Вт. Это означает, что в очереди имеется не более 2 ^ W различных приоритетов, и сложность алгоритма Дейкстры, использующего этот тип очереди приоритетов, составляет O (| E | W).
Поскольку вы не хотите выделять 2 ^ W сегмента, дерево связанных списков Patricia создаст жизнеспособную очередь с приоритетами для вашего случая.