Реализация и время выполнения
перебрать все ребра между 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.
Еще по теме Реализация и время выполнения:
- Вторая зрелость – время реализации своей мечты
- Статья 849. Права заказчика во время выполнения работы
- Статья 1196. Возмещение вреда, причиненного физическому лицу во время выполнения им договорных обязательств
- Время сейчас такое – время мудрости пришло!
- 14. 4. Рабочее время и время отдыха
- Зарубка на носу Дай время себе, дай время ребенку
- 3.3. Дальнейшая реализация проекта
- Глава 6. Реализация права
- 4.2. Реализация
- 4. Реализация прав по ипотеке
- 10. Реализация заложенного имущества
- РЕАЛИЗАЦИЯ МЫСЛЕННОГО ПРЕДСТАВЛЕНИЯ
- Механизм реализации личности
- Практическая реализация.