Изменения
→Реализация
p[u] = v
key[u] = w(v, u)
Q.decreaseKey(Q, u, key[u])
Ребра дерева восстанавливаются из его неявного вида после выполнения алгоритма.
Операцию <tex>decreaseKey</tex> сделать для приоритетной очереди на обычной кучи немного проблематично, поэтому есть два варианта. Первый, написать приоритетную очередь на какой-то сложной куче, например, биноминальной или фибоначчиевой. Второй, изменять значение ключа у вершины u, для которой вызвали <tex>decreaseKey</tex>, непосредственно в очереди, после чего делать процедуру просеивания вверх(подробнее об этой процедуре можно прочитать [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D0%B0%D1%8F_%D0%BA%D1%83%D1%87%D0%B0#siftUp здесь]). Для быстрого доступа к позиции данной вершины u в очереди, нужно дополнительно хранить указатель на эту позицию и не забывать его изменять при процедурах восстановления свойств кучи.
==Пример==
