Алгоритм Дейкстры поиска путей в графе. Как реализовать с помощью приоритетной очереди?

[Zefick]

Вот задача: найти радиус графа с помощью алгоритма Дейкстры. Как работает алгоритм я знаю. Единственная проблема - надо реализовать его с использованием приритетной очереди (двоичной кучи, пирамиды, что почти одно и то же).
Приоритетная очередь у меня есть. Я могу загнать в неё все вершины и доставать ту, у которой метка меньше всех. Только вот проблема: надо в процессе обхода смежных вершин осуществлять так называемые релаксации, которые уменьшают метку вершин. Естественно, изменение меток должно отражаться и в очереди, только я не нашёл способа это сделать. Я даже могу изменять конкретный элемент очереди, по индексу в ней, только индекс неизвестен, потому что элементы в процессе извлечения и изменения перемешиваются.
Если кто-то хочет ознакомиться с алгоритмом дейкстры, то вот ссылка: http://ru.wikipedia.org/wiki/Алгоритм_Дейкстры