Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Глава 21. Кратчайшие пути. короткое и толстое, a MST - вообще не короткое и не толстое, равно как и не высокое и не тонкое.
|
|
короткое и толстое, a MST - вообще не короткое и не толстое, равно как и не высокое и не тонкое.
Мы уже рассматривали четыре различных реализации PFS. Первая — это классическая реализация насыщенного графа, которая содержит в себе алгоритм Дейкстры и алгоритм Прима поиска MST (программа 20.6). Три других реализации, отличающиеся содержимым очереди с приоритетами, суть реализации разреженных графов:
■ Ребра бахромы (программа 18.10).
■ Вершины бахромы (программа 20.7).
■ Все вершины (программа 21.1).
Первая реализация имеет, прежде всего, познавательную ценность, тогда как вторая является наиболее совершенной, а третья, возможно, — наиболее простой. В этих рамках уже содержится описание 16 различных реализаций классических алгоритмов поиска на графе — когда мы рассматриваем различные реализации очередей с приоритетами, происходит дальнейшее нарастание возможных вариантов. Это быстрое увеличение сетей, алгоритмов и реализаций подчеркивает полезность общих формулировок производительности в свойствах от 21.4 до 21.6, что также приводится в таблице 21.2.
Таблица 21.2 Стоимость реализаций алгоритма Дейкстры_______________________
Эта таблица подводит итог стоимости (наихудшее значение продолжительности исполнения) различных реализаций алгоритма Дейкстры. При соответствующей реализации очередей с приоритетами алгоритм выполняется за линейное время (время, пропорциональное V2 для насыщенных сетей, и значению Е- для разреженных сетей), за исключением очень разреженных сетей.
Оценка
худшего
Алгоритм случая Комментарий
Классический V2 Оптимален для насыщенных графов
PFS, заполненное бинарное дерево Е lg V Самая простая реализация
PFS, полное бинарное дерево ElgV Консервативная верхняя оценка
для представления бахромы
PFS, полное d-арное дерево Е lgdV Линейный, если граф не слишком
разреженный
Как правило, фактическое время нахождения кратчайших путей для алгоритмов MST, скорее всего, ниже оценок времени для худшего случая, прежде всего, потому, что большинство ребер не требуют операции уменьшения ключей. На практике, за исключением наиболее разреженных графов, мы считаем, что время выполнения не является линейным.
Название алгоритма Дейкстры обычно используется для обозначения как абстрактного метода построения SPT путем добавления вершин в порядке их расстояния от источника, так и его реализации как алгоритма со временем, пропорциональным V2, для построения матрицы смежности, поскольку Дейкстра представил и то, и другое в своей статье, опубликованной в 1959 г. (а также показал, что тем же методом можно вычислить и MST). Увеличение производительности на разреженных графах связано с более поздними усовершенствованиями в технологии АТД и реализациях очереди с приоритетами, которые не являются характерными для задач поиска кратчайших путей. Более высокая про-
Часть 5. Алгоритмы на графах
изводительность алгоритма Дейкстры - это одно из наиболее важных свойств этой технологии (см. раздел ссылок). Как и в случае с MST, для указания на специфические комбинации мы применяем такие термины, как, например, " реализация алгоритма Дейкстры с PFS с использованием полного d-арного дерева".
В разделе 18.8 было показано, что в невзвешенных неориентированных графах использование нумераций приоритетов в прямом порядке обхода вершин графа приводит к тому, что очередь с приоритетами действует как очередь FIFO и приводит к BFS. Алгоритм Дейкстры дает нам другую реализацию BFS: когда все веса ребер равны 1, а обход вершин производится в порядке номеров ребер на кратчайшем пути к стартовой вершине. В этом случае очередь с приоритетами не действует в точности как очередь FIFO, поскольку элементы с равными приоритетами не обязательно изымаются из очереди в том порядке, в котором они в нее помещались.
Каждая из этих реализаций помещает в индексированный вершинами вектор spt ребра дерева кратчайших путей SPT (Shortest Path Tree) из вершины 0, а в индексированный вершиной вектор wt — длины кратчайших путей в каждую вершину в SPT; кроме того, каждая реализация имеет функции-элементы, обеспечивающие доступ к этим данным со стороны клиентов. Как обычно, имеется возможность построить различные функции обработки графов и классы, основанные на этих первичных данных (см. упражнения 21.21-21.28).