Главная » Деревья

Алгоритм построения дерева путей

Содержание
  1. Алгоритмы построения дерева кратчайших путей: от простых до сложных
  2. Алгоритм Дейкстры
  3. Описание алгоритма
  4. Пример
  5. Алгоритм Беллмана-Форда
  6. Описание алгоритма
  7. Пример
  8. Алгоритм Флойда-Уоршелла
  9. Описание алгоритма
  10. Пример
  11. Заключение
  12. Три алгоритма на графах

Алгоритмы построения дерева кратчайших путей: от простых до сложных

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

Алгоритм Дейкстры

Алгоритм Дейкстры – это один из наиболее распространенных и известных алгоритмов построения дерева кратчайших путей. Он был разработан нидерландским ученым Эдсгером Дейкстрой в 1959 году и представляет собой жадный алгоритм, который работает только с неотрицательными весами ребер.

Описание алгоритма

Алгоритм Дейкстры начинает работу с одной стартовой вершины и последовательно просматривает все вершины графа, обновляя значения кратчайших расстояний до каждой из вершин. На каждом шаге алгоритма выбирается вершина с наименьшим расстоянием от стартовой вершины, после чего обновляются расстояния до всех вершин, смежных с выбранной. Повторив этот процесс для всех вершин графа, можно построить дерево кратчайших путей.

Пример

Рассмотрим граф, изображенный на рисунке:

И попробуем применить алгоритм Дейкстры для построения дерева кратчайших путей, начиная с вершины A.

  1. Помечаем вершину A и устанавливаем ее расстояние до себя равным 0.
  2. Рассчитываем расстояния до смежных вершин: B – 3, C – 2 и D – 6.
  3. Выбираем вершину C с наименьшим расстоянием и помечаем ее.
  4. Рассчитываем расстояния до смежных вершин: A – 2, B – 1 и E – 4.
  5. Выбираем вершину B с наименьшим расстоянием и помечаем ее.
  6. Рассчитываем расстояния до смежных вершин: A – 3, C – 1, D – 3 и E – 5.
  7. Выбираем вершину D с наименьшим расстоянием и помечаем ее.
  8. Рассчитываем расстояния до смежных вершин: A – 6, B – 3 и E – 6.
  9. Выбираем вершину E с наименьшим расстоянием и помечаем ее.
  10. Рассчитываем расстояния до смежных вершин: C – 4, B – 5 и D – 6.
  11. Все вершины помечены, построение дерева кратчайших путей завершено. Результат можно увидеть на рисунке:

Алгоритм Беллмана-Форда

Алгоритм Беллмана-Форда также является широко используемым алгоритмом для построения дерева кратчайших путей. Он был разработан двумя учеными – Ричардом Беллманом и Лестером Фордом – в 1958 году и подходит для графов с отрицательными весами ребер.

Описание алгоритма

Алгоритм Беллмана-Форда работает итеративно и на каждой итерации обновляет значения расстояний до каждой вершины графа. На первой итерации расстояние до стартовой вершины устанавливается равным 0, а до всех остальных вершин – бесконечности. Далее на каждой следующей итерации алгоритма обновляются расстояния до всех вершин, смежных с обрабатываемой.

Если на n-ой итерации произошли обновления расстояний, то в графе есть цикл отрицательного веса, и алгоритм завершается с ошибкой. В противном случае построение дерева кратчайших путей завершается.

Читайте также:  Масло розового дерева простуда

Пример

Рассмотрим граф с отрицательными весами ребер, изображенный на рисунке:

И попробуем применить алгоритм Беллмана-Форда для построения дерева кратчайших путей, начиная с вершины A.

  1. Устанавливаем расстояние до вершины A равным 0, а до всех остальных вершин – бесконечности.
  2. Рассчитываем расстояния до смежных вершин: B – 5 и C – 8.
  3. Рассчитываем расстояния до смежных вершин: B – 2, C – 5 и D – 4.
  4. Рассчитываем расстояния до смежных вершин: B – 2, C – 5 и E – 7.
  5. Рассчитываем расстояния до смежных вершин: C – 2, D – 1 и E – 4.
  6. Рассчитываем расстояния до смежных вершин: E – 2.
  7. Все вершины помечены, построение дерева кратчайших путей завершено. Результат можно увидеть на рисунке:

Алгоритм Флойда-Уоршелла

Алгоритм Флойда-Уоршелла является алгоритмом динамического программирования, который позволяет решить задачу о кратчайших путях между всеми парами вершин графа. Он был разработан Робертом Флойдом и Стивеном Уоршеллом в 1962 году.

Описание алгоритма

Алгоритм Флойда-Уоршелла работает в несколько этапов. На каждом этапе алгоритма рассчитывается матрица расстояний между всеми парами вершин, учитывая только промежуточные вершины в пределах определенного диапазона номеров.

На первом этапе диапазон номеров промежуточных вершин состоит только из стартовых вершин, на втором – из стартовых вершин и вершин, номера которых не превышают 1, на третьем – из всех вершин.

Пример

Рассмотрим граф, изображенный на рисунке:

И попробуем применить алгоритм Флойда-Уоршелла для построения матрицы расстояний между всеми парами вершин.

Таким образом, мы получаем матрицу расстояний между всеми парами вершин. Если требуется построить дерево кратчайших путей для каждой вершины графа, то можно использовать полученную матрицу и применить алгоритм, описанный выше для каждой стартовой вершины.

Заключение

Алгоритмы построения дерева кратчайших путей представляют собой одну из фундаментальных задач графовой теории. Каждый алгоритм имеет свои особенности и подходит для решения определенных типов задач. Некоторые из них могут работать только с неотрицательными весами ребер, другие – с отрицательными. В зависимости от поставленной задачи можно выбрать подходящий алгоритм или же комбинировать их для достижения оптимального результата.

Источник

Три алгоритма на графах

Пусть G=(V,E) — ориентированный граф , для каждого ребра e \in Eкоторого указана его (неотрицательная) длина : c(e) >= 0 . Тогда длина пути p=v1,v2, . , vk+1 определяется как сумма длин ребер, входящих в этот путь : c(p) = \sum_<i=1 data-lazy-src=

Мы рассмотрим алгоритм построения дерева кратчайших путей и определения их длин, предложенный в 1959г. Е. Дейкстрой. Его идея следующая: перед каждым этапом известно множество отмеченных вершин S , для которых кратчайшие пути найдены ранее; тогда на очередном этапе к нему добавляется вершина w , с самым коротким путем из a , проходящим по множеству S ; после этого пересчитываются длины кратчайших путей из a в оставшиеся вершины из V \ S с учетом новой вершины w . Длина текущего кратчайшего пути из a в v , проходящего по множеству S , заносится в ячейку D[v] массива D . В конце работы в этом массиве отыскиваются длины соответствующих кратчайших путей . Для определения дерева кратчайших путей служит массив ОТЕЦ , его элемент ОТЕЦ[v] содержит ссылку на вершину, из которой кратчайший путь приходит в v .

Вход: G=(V,E) — ориентированный граф , c(u,v) >= 0 — длина ребра (u,v) \in E(если (u,v) \notin E, то считаем, что c(u,v) = \infty )и исходная вершина a \in V.

a \in V

Пример 11.3. Рассмотрим работу этого алгоритма на нагруженном графе G=(V=, E) и выделенной вершине . Зададим длины ребер матрицей C= (cuv) , где элемент cuv=c(u,v) :

\[\left( \begin</p data-lazy-src=

Дерево кратчайших путей из вершины a задается массивом ОТЕЦ . Оно представлено на рис. 11.5.

Теорема 11.4. (о корректности алгоритма Дейкстры )

Алгоритм Дейкстры строит дерево кратчайших путей из вершины a во все достижимые из нее вершины и для каждой такой вершины v определяет длину D[v] кратчайшего пути в нее из a .

Читайте также:  Картина из картона дерево

Доказательство Докажем по индукции, что после каждого этапа алгоритма выполнены следующие условия:

  • для любой вершины v \in Sвеличина D[v] равна длине кратчайшего пути из a в v ;
  • для любой вершины v \in V \setminus Sвеличина D[v] равна длине кратчайшего пути из a в v , проходящего по множеству S ;
  • для каждой вершины v дерева T , задаваемого массивом ОТЕЦ , длина пути из корня a в v равна D[v] .

Эти три условия очевидно выполняются после инициализации в строках 1- 5.

u\ne w

Предположим теперь, что они выполнены перед началом k -го этапа. Пусть w — вершина , добавляемая к S на k -ом этапе. По предположению, D[w] — длина кратчайшего пути из a в w , все вершины которого, кроме w , входят в S . Предположим, что есть другой более короткий путь p из a в w . Зафиксируем на этом пути первую вершину u , не входящую в S . По выбору p . Поэтому путь p разбивается на две непустые части: путь p1 из a в u и путь p2 из u в w . Но по выбору w мы имеем, что длина p1 >= D[u] >= D[w] . Так как длина p2 неотрицательна, то длина p >= D[w] , т.е. этот путь не короче пути, представленного в дереве T . Таким образом, D[w] — это длина кратчайшего пути из a в w . Следовательно, условие (а) выполнено и после k -го этапа.

Рассмотрим теперь произвольную вершину u \in V \setminus (S \cup \< w\ data-lazy-src=

Так как после завершения алгоритма S = V , то в завершающем дереве T представлены кратчайшие пути из a во все достижимые из нее вершины, а массив D содержит длины этих путей. Значение указывает на то, что вершина u не достижима из вершины a .

u \in (V\setminus S)

Замечание о сложности. На каждом этапе (исполнении тела основного цикла в стр. 6 — 13) одна вершина добавляется во множество S . Поэтому таких этапов не более |V| . Чтобы выбрать в массиве D вершину w с минимальным D[w] (стр. 7), требуется не более |V| шагов. Перевычисление D[u] для каждой из вершин требует константного числа операций, поэтому весь цикл в стр. 9 — 12 потребует не более c |V| шагов. Отсюда получаем, что для некоторой константы c время выполнения алгоритма Дейкстры не превышает c |V| 2 . Поскольку размер любого представления исходного графа не меньше |V| , то алгоритм работает в квадратичное время (от размера входа).

Источник

Оцените статью