Разработка алгоритма

В 1959 году Эдгар Дейкстра предложил очень простой жадный алгоритм для решения задачи нахождения кратчайшего пути с одним источником. Мы начнем с описания алгоритма, который просто находит длину кратчайшего пути от s к каждому из остальных узлов графа; после этого можно будет легко получить сами пути.
Алгоритм хранит множество S вершин u, для которых было определено расстояние d(и) кратчайшего пути от s; это множество представляет «исследован- ную» часть графа. Изначально S = {s}, а d(s) = 0. Затем для каждого узла v V- S

определяется кратчайший путь, который может быть построен перемещением по пути в исследованной части S к некоторому и S, за которым следует одно ребро

(u, v). Далее рассматривается характеристика d'(v) = mine=(u vyu^s d(и) + le. Алгоритм выбирает узел v V - S, для которого эта величина минимальна, добавляет v в S

и определяет d(v) как значение d'(v).

Алгоритм Дейкстры (G, i)

Пусть S - множество исследованных узлов

Для каждого u e S хранится расстояние d(u)

Изначально S = {s} и d(s) = 0 Пока SФ V

Выбрать узел v ⅜ S с хотя бы одним ребром из S, для которого значение d'(v) = mine=(u v).uES d(u) + ie минимально

Добавить v в S и определить d(v) = d'(v)

Конец Пока

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

Путь Pv неявно представляется этими ребрами: если (u, v) — ребро, сохраненное для v, то Pv — это (рекурсивно) путь Pu, за которым следует одно ребро (u, v). Иначе говоря, чтобы построить Pv, мы просто начинаем с v; переходим по ребру, сохраненному для v, в обратном направлении к u; затем переходим по ребру, сохраненному для u, в обратном направлении к его предшественнику, и т. д., пока не доберемся до s. За- метьте, что узел s должен быть достижим, так как обратный переход от v посещает узлы, добавлявшиеся в S ранее и ранее.

Чтобы лучше понять, как работает алгоритм, рассмотрите «снимок» его выпол- нения на рис. 4.7. На момент создания «снимка» были выполнены две итерации: первая добавила узел u, а вторая — узел v. В предстоящей итерации будет добав- лен узел X, потому что с ним достигается наименьшее значение d'(х); благодаря ребру (u, х) имеем d'(х)=d(u) + l = 2. Обратите внимание: попытка добавить у или z в множество S в этой точке приведет к неправильным расстояниям кратчайших путей; в конечном итоге они будут добавлены из-за ребер от х.

Рис. 4.7. Снимок выполнения алгоритма Дейкстры. Следующим узлом, добавляемым в множество S, будет узел x (из-за пути через u)


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

Еще по теме Разработка алгоритма:

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