Анализ алгоритма

Из примера видно, что алгоритм Дейкстры работает правильно и избегает ловушек: добавление в множество S неправильного узла может привести к переоценке рас- стояния кратчайшего пути к этому узлу. Остается ответить на вопрос: всегда ли при добавлении алгоритмом Дейкстры узла v мы получаем истинное расстояние кратчайшего пути к v?

Ответ доказывает правильность алгоритма и то, что пути Pu действительно являются кратчайшими.

Алгоритм Дейкстры является жадным в том смысле, что он всегда строит кратчайший новый путь s-v, состоящий из пути из S, за которым следует одно ребро. Для доказательства правильности будет использована разно- видность первого метода анализа: мы продемонстрируем, что это решение «идет впереди» всех остальных. Для этого мы покажем методом индукции, что каждый выбираемый им путь к узлу v будет короче любого другого пути к v.

(4.14) Рассмотрим множество S в любой точке выполнения алгоритма. Для каждого узла и S путь Pu является кратчайшим путем s-и.

Обратите внимание: этот факт немедленно доказывает правильность алгоритма Дейкстры, так как его можно применить к моменту завершения алгоритма, когда S включает все узлы.

Доказательство. Для доказательства будет использоваться индукция по размеру S. Случай | S | = 1 тривиален: в этом состоянии S = {s} и d(s) = 0. Предпо- ложим, утверждение истинно для |S| = к при некотором значении к > 1; теперь S увеличивается до размера к + 1 добавлением узла v. Пусть (u, v) — последнее ребро пути s-v Pv.

Согласно индукционной гипотезе, Pu является кратчайшим путем s-и для всех и ^ S. Теперь возьмем любой другой путь s-v P; мы хотим показать, что он по крайней мере не короче Pv. Чтобы достичь узла v, путь P должен где-то выйти из множества S; пусть у — первый узел P, не входящий в S, и x i(Px) = d(x). Следовательно, подпуть P к узлу у имеет длину l(P') + i(x, у) > d(x) + i(x, у) > d'(у), и полный путь P по край- ней мере не короче этого подпути.

Наконец, раз алгоритм Дейкстры выбрал v на этой итерации, мы знаем, что d'(у) > d'(v) = i(Pv). Объединение этих неравенств показывает, что £(P) > i(P') + i(x,у) > i(Pv). ■

Приведем пару замечаний относительно алгоритма Дейкстры и его анализа. Во-первых, алгоритм не всегда находит кратчайшие пути, если некоторые ребра имеют отрицательную длину. (А вы видите, где нарушается работа алгоритма?) Отрицательная длина ребер встречается во многих задачах нахождения кратчай- шего пути, и в таких ситуациях требуется более сложный алгоритм, предложен- ный Беллманом и Фордом. Мы рассмотрим этот алгоритм, когда займемся темой динамического программирования.

Второе замечание заключается в том, что алгоритм Дейкстры в некотором смысле еще проще приведенного описания. Алгоритм Дейкстры в действитель- ности является «непрерывной» версией алгоритма поиска в ширину для обхода графа; это можно пояснить физической аналогией. Допустим, ребра G образуют

систему труб, заполненных водой и состыкованных в узлах; каждое ребро e об- ладает длиной le и фиксированным поперечным сечением. Теперь допустим, что в узле 5 падает капля воды, в результате чего от 5 начинает расходиться волна. Так как волна распространяется от 5 с постоянной скоростью, расширяющаяся сфера волнового фронта достигает узлов в порядке возрастания их расстояния от 5. Инту- иция подсказывает, что путь, по которому проходит фронт для достижения любого узла v, является кратчайшим (и это действительно так). Как нетрудно убедиться, именно этот путь v будет найден алгоритмом Дейкстры, а расширяющаяся волна доходит до узлов в том же порядке, в котором они обнаруживаются алгоритмом Дейкстры.

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

Еще по теме Анализ алгоритма:

  1. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  4. АЛГОРИТМ
  5. АЛГОРИТМ УДАЧИ
  6. Алгоритм исцеления:
  7. Алгоритм избавления от боли
  8. 2. Специфика и алгоритмы работы с источниками.
  9. Алгоритм обработки результатов.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. 2. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.
  12. Принципы анализа происшествия.
  13. АНАЛИЗ