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