Алгоритм Дейкстры

Заполнить массив нулями.
Каждой вершине приписать в качестве ключа — максимально возможное число (оно должно быть больше, чем длина наибольшего из кратчайших путей в графе; в процессе вычислений это число будет уменьшаться и в итоге заменится на длину кратчайшего пути из вершины в вершину ).
Организовать приоритетную очередь из вершин графа, взяв в качестве ключей величины , .
Заменить ключ вершины на 0.
Пока очередь не пуста, выполнять операции .
Выбрать (с удалением) из приоритетной очереди элемент с минимальным ключом.
Для каждой вершины , смежной с , выполнить операции .
Вычислить величину .
Если , то уменьшить ключ элемента

на величину и заменить старое значение величины на .

Упражнение

Напишите на каком-либо алгоритмическом языке реализацию алгоритма Дейкстры с использованием -кучи и испытайте ее на тестовых примерах при различных значениях .

Содержание Назад