|
|
Использование очереди по приоритетам в алгоритмах Прима и Дейкстры.
Алгоритмы Прима и Дейкстры, в их классической реализации, являются фактически линейными для насыщенных графов, ведь время их выполнения есть O(V2), где V - количество вершин в графе, а в насыщенных графа количество ребер пропорционально V2. Но для разреженных графов с большим количеством вершин классические реализации крайне не эффективны. Чтобы добиться большей эффективности нужно использовать подходящие структуры данных. Так как графы разреженные, для представления графа лучше всего использовать списки смежных вершин.
При реализации обоих алгоритмов обычно используется массив - в алгоритме Дейкстры для хранения расстояний от вершины-источника, а в алгоритме Прима - для хранения расстояний от MST. На каждом шаге обоих алгоритмов в массиве ищется минимум. Вершина соответствующая этому минимуму помещается в формируемое дерево, и соответствующим образом корректируется значения расстояний в массиве. В классической реализации обоих алгоритмов действительно используется массив, что в какой-то мере соответствует очереди по приоритетам на базе неупорядоченного массива. Если же использовать индексированную очередь по приоритетам, которая позволяет быстро (хотя бы за логарифмическое время) выполнять операции нахождения и удаления минимума, вставки в очередь и изменение приоритета, тогда время выполнения алгоритмов станет практически линейным.
|
|