Реализация и время выполнения

Обсуждение алгоритма Дейкстры завершается анализом его времени выполнения. Для графа с n узлами цикл состоит из n - 1 итераций, так как каждая итерация до- бавляет в S новый узел v. С эффективностью выбора правильного узла v дело обсто- ит сложнее.
Первая мысль — при каждой итерации рассмотреть новый узел v S,

перебрать все ребра между S и v с вычислением минимума mine=(u vyu^s d(u) + le, чтобы выбрать узел v с наименьшим значением. Для графа с m ребрами вычисле- ние минимумов будет выполняться за время O(m), так что полученная реализация будет выполняться за время O(mn).

Правильный выбор структуры данных позволяет существенно улучшить ре- зультат. Прежде всего, значения минимумов d'(v) = mine=(u v).u⅞S d(u) + le следует явно хранить для каждого узла v V- S, чтобы не вычислять их заново при каждой итерации. Также эффективность можно повысить посредством хранения узлов V-S в приоритетной очереди с ключами d'(v). Приоритетные очереди рассматривались в главе 2; эти структуры данных предназначены для хранения множеств из n эле- ментов с ключами. Приоритетная очередь обеспечивает эффективное выполнение вставки элементов, удаления элементов, изменения ключей и извлечения элемен- тов с минимальным ключом. Нам понадобятся третья и четвертая из перечислен- ных операций:ChangeKey и ExtractMin.

Как реализовать алгоритм Дейкстры с использованием приоритетной очереди? Узлы V помещаются в приоритетную очередь с ключом d'(v) для v V. Для вы-

бора узла v, который должен быть добавлен в множество S, понадобится операция ExtractMin. Чтобы понять, как обновлять ключи, рассмотрим итерацию, в которой узел v добавляется в S; пусть w ⅜ S — узел, остающийся в приоритетной очереди. Что нужно сделать для обновления значения d'(w)? Если (v, w) не является ре- бром, то делать ничего не нужно: множество ребер, рассматриваемых в минимуме mine=(u v).ueS d(u) + le, в точности совпадает до и после добавления v в S. С другой стороны, если e' = (v,w) E, то новым значением ключа будет miп(d'(w), d(v) + le,). Если d'(w) > d(v) + l, то нужно использовать операцию ChangeKey для соответству- ющего изменения ключа узла w. Операция ChangeKey может выполняться не более одного раза на ребро, при добавлении «хвоста» e' в S. Таким образом, мы получаем следующий результат.

(4.15) При использовании приоритетной очереди алгоритм Дейкстры для гра- фа с n узлами и m ребрами может быть реализован с выполнением за время О(m) с добавлением времени n операций ExtractMin и m операций ChangeKey.

При реализации приоритетной очереди на базе кучи (см. главу 2) все операции будут выполняться за время О(log n). Таким образом, общее время выполнения составит O(m log n).

4.5.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Реализация и время выполнения:

  1. Вторая зрелость – время реализации своей мечты
  2. Статья 849. Права заказчика во время выполнения работы
  3. Статья 1196. Возмещение вреда, причиненного физическому лицу во время выполнения им договорных обязательств
  4. Время сейчас такое – время мудрости пришло!
  5. 14. 4. Рабочее время и время отдыха
  6. Зарубка на носу Дай время себе, дай время ребенку
  7. 3.3. Дальнейшая реализация проекта
  8. Глава 6. Реализация права
  9. 4.2. Реализация
  10. 4. Реализация прав по ипотеке
  11. 10. Реализация заложенного имущества
  12. РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ
  13. Механизм реализации личности
  14. Практическая реализация.