Алгоритм дейкстры программа. Нахождение кратчайших путей от заданной вершины до всех остальных вершин алгоритмом дейкстры. Математическое описание алгоритма

5.4.3. Задача о кратчайшем пути и алгоритм Дейкстры ее решения

Пусть задан орграф G (V , E ), каждой дуге которого поставлено в соответствие число
, называемое длиной дуги .

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

Вариант 1. Найти длины кратчайших путей (путей минимальной длины) и сами пути от фиксированной вершины s до всех остальных вершин графа.

Вариант 2. Найти длины кратчайших путей и сами пути между всеми парами вершин данного графа.

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

Заметим, что если кратчайший путь существует, то любой его подпуть – это тоже кратчайший путь между соответствующими вершинами.

Алгоритм Дейкстры решения задачи о кратчайшем пути.

Алгоритм работает с дугами положительной длины и определяет кратчайшие пути от фиксированной вершины s до всех остальных вершин графа. Обозначим эти вершины v 1 , v 2 ,…, v n .

Определение. Назовем вершину u лежащей ближе к вершине s , чем вершина v , если длина кратчайшего пути от s до u меньше длины кратчайшего пути от s до v . Будем говорить, что вершины u и v равноудалены от вершины s , если длины кратчайших путей от s до u и от s до v совпадают.

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

Если длины дуг – положительные числа, то

ближайшая к s вершина – она сама. Длина кратчайшего пути от s до s равна 0;

ближайшая к s вершина, отличная от s , лежит от s на расстоянии одной дуги  самой короткой из всех дуг, выходящих из вершины s ;

любая промежуточная вершина кратчайшего пути от s до некоторой вершины v лежит ближе к s , чем конечная вершина v ;

кратчайший путь до очередной упорядоченной вершины может проходить только через уже упорядоченные вершины.

Пусть алгоритм уже упорядочил вершины v 1 , v 2 … v k . Обозначим через
,
длину кратчайшего пути до вершины v i .

Рассмотрим все дуги исходного графа, которые начинаются в одной из вершин множества
и оканчиваются в еще неупорядоченных вершинах. Для каждой такой дуги, например
, вычислим сумму
. Эта сумма равна длине пути из s в y , в котором вершина v i есть предпоследняя вершина, а путь из s в v i – кратчайший из всех путей, соединяющих s и v i .

Этим самым определены длины всех путей из s в еще не упорядоченные вершины, в которых промежуточными вершинами являются только вершины из числа k ближайших к s . Пусть кратчайший из этих путей оканчивается на вершине w . Тогда w и есть
по близости к s вершина.

Технически действия по алгоритму Дейкстры осуществляются при помощи аппарата меток вершин. Метка вершины v обозначается как
. Всякая метка – это число, равное длине некоторого пути от s до v . Метки делятся на временные и постоянные. На каждом шаге только одна метка становиться постоянной. Это означает, что ее значение равно длине кратчайшего пути до соответствующей вершины, а сама эта вершина упорядочивается. Номер очередной упорядоченной вершины обозначим буквой р .

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

Шаг 1. (Начальная установка) . Положить
и считать эту метку постоянной. Положить
,
и считать эти метки временными. Положить
.

Шаг 2. (Общий шаг). Он повторяется n раз, пока не будут упорядочены все вершины графа.

Пересчитать временную метку
всякой неупорядоченной вершины v i , в которую входит дуга, выходящая из вершины р, по правилу

Выбрать вершину с минимальной временной меткой. Если таких вершин несколько, выбрать любую.

Пусть w - вершина с минимальной временной меткой. Считать метку
постоянной и положить
.

Шаги алгоритма Дейкстры удобно оформлять в таблице, каждый столбец которой соответствует вершине графа. Строки таблицы соответствуют повторению общего шага.

Пример . Для графа на рис. 4. найти кратчайшие пути от вершин
до всех остальных вершин графа. Ребра означают две разнонаправленные дуги одинаковой длины.

Решение. В табл. 1 записаны метки вершин на каждом шаге. Постоянные метки помечены знаком «+». Подробно опишем, как вычисляются метки вершин.

Из вершины 1 выходят дуги в вершины 2, 5, 6. Пересчитываем метки этих вершин и заполним вторую строку таблицы.

Метка вершины 6 становиться постоянной,
.

Из вершины 6 выходят дуги в еще неупорядоченные вершины 2, 5, 8, 9. Пересчитываем их временные метки

Заполняем 3 строку таблицы. Минимальная из временных меток равна 3 (метка вершины 9),
.

Из вершины 9 выходят дуги в еще неупорядоченные вершины 5, 8, 11, 12. Тогда

Заполняем четвертую строку таблицы. В этой строке две вершины  2 и 12 имеют минимальные временные метки, равные 4. Сначала упорядочим, например, вершину 2. Тогда на следующем шаге будет упорядочена вершина 12.

Таблица 1

Итак,

Из вершины 2 выходят дуги в еще неупорядоченные вершины 3, 4, 5. Пересчитываем временные метки этих вершин

Заполняем 5 строку таблицы. Минимальная из временных меток равна 4 (метка вершины 12),
.

Заполняем 6 строку таблицы. Минимальная из временных меток равна 5 (метка вершины 5),
.

Заполняем 7 строку таблицы. Становиться постоянной метка вершины 8 (она равна 5),
.

Вершина 11 упорядочивается.

Из вершины 11 выходят дуги в неупорядоченные вершины 7, 10. Пересчитываем временные метки этих вершин

Вершина 4 получает постоянную метку.

Из вершины 4 выходят дуги в неупорядоченные вершины 3, 7. Пересчитываем временные метки

Упорядочиваем вершину 3.

Заполняем 12 строку таблицы. На этом шаге упорядочиваем последнюю неупорядоченную вершину 10.

Построение дерева кратчайших путей.

Дерево кратчайших путей – это ориентированное дерево с корнем в вершине S . Все пути в этом дереве – кратчайшие для данного графа.

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

Построим дерево кратчайших путей для нашего примера.

Сначала включаем в дерево корень – вершину 1. Затем в дерево включается дуга (1,6). Следующей была упорядочена вершина 9, длина кратчайшего пути до которой равна 3. Первый раз число 3 появилось в третьей строке, которая заполнялась при
. Следовательно, вершина 6 – предпоследняя вершина кратчайшего пути до вершины 9. Включаем в дерево дугу (6,9) длины 1.

Затем была упорядочена вершина 2 с длиной кратчайшего пути, равной 4. Это число первый раз появилось в третьей строке, которая заполнялась при
. Следовательно, кратчайший путь во вторую вершину проходит по дуге (6,2). Включаем в дерево дугу (6,2) длины 2.

Далее была упорядочена вершина 12,
. Первый раз число 4 появляется в четвертой строке, которая заполнялась при
. В дерево включается дуга (9,12) длины 1. Полное дерево кратчайших путей показано на рис. 5.

Алгоритм Дейкстры может ошибаться, если в графе есть дуги отрицательной длины. Так, отыскивая кратчайшие пути от вершины s =1 для графа на рис. 6, алгоритм сначала упорядочит вершину 3, затем вершину 2 и закончит работу. При этом этот кратчайший путь до вершины 3, с точки зрения алгоритма Дейкстры,  это дуга (1,3) длины 3.

На самом деле, кратчайший путь до вершины 3 состоит из дуг (1,2) и (2,3), длина этого пути равна 5+(-3)=2.

Из-за наличия дуги (2,3) отрицательной длины –3 оказались нарушенными следующие базовые принципы:

ближайшая к s вершина лежит от нее на расстоянии двух дуг, а не одной;

промежуточная вершина кратчайшего пути 1-2-3 (вершина 2) лежит дальше от вершины 1 (на расстоянии 5), чем конечная вершина пути 3.

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

Алгори́тм Де́йкстры (Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием Сначала Кратчайший Путь (Shortest Path First ).

Примеры

Вариант 1. Дана сеть автомобильных дорог, соединяющих города Новосибирской области. Некоторые дороги односторонние. Найти кратчайшие пути от Новосибирска до каждого города области (если двигаться можно только по дорогам).

Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула.

Формальное определение

Дан взвешенный ориентированный граф G (V , E ) без петель и дуг отрицательного веса. Найти кратчайшие пути от некоторой вершины a графа G до всех остальных вершин этого графа.

Неформальное объяснение

Каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a . Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация . Метка самой вершины a полагается равной 0, метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещённые.

Шаг алгоритма . Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u , имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, в которые ведут рёбра из u , назовем соседями этой вершины. Для каждого соседа вершины u , кроме отмеченных как посещённые, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученное значение длины меньше значения метки соседа, заменим значение метки полученным значением длины. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг алгоритма.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке. Пусть требуется найти расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями - пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.

Первый шаг . Рассмотрим шаг алгоритма Дейкстры для нашего примера. Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6.

Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1, значение её метки, и длины ребра, идущего из 1-ой в 2-ую, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит (то, что это действительно так, впервые доказал Э. Дейкстра). Вычеркнем её из графа, чтобы отметить, что эта вершина посещена.

Второй шаг . Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 - вершина 3, так имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9<17, поэтому метка не меняется.

Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояние до 2-ой вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещенную.

Третий шаг . Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Дальнейшие шаги . Повторяем шаг алгоритма для оставшихся вершин. Это будут вершины 6, 4 и 5, соответственно порядку.

Завершение выполнения алгоритма . Алгоритм заканчивает работу, когда вычеркнуты все вершины. Результат его работы виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.

Алгоритм

Обозначения

V - множество вершин графа

E - множество ребер графа

w [ij ] - вес (длина) ребраij

a - вершина, расстояния от которой ищутся

U - множество посещенных вершин

d [u ] - по окончании работы алгоритма равно длине кратчайшего пути изa до вершиныu

p [u ] - по окончании работы алгоритма содержит кратчайший путь изa вu

Псевдокод

Присвоим

Для всех отличных от a

присвоим

Пусть - вершина с минимальнымd [v ]

Для всех таких, что

еслиd [u ] >d [v ] +w [vu ]то

Описание

В простейшей реализации для хранения чисел d [i ] можно использовать массив чисел, а для хранения принадлежности элемента множеству U - массив булевых переменных.

В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бо́льшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.

На каждом шаге цикла мы ищем вершину с минимальным расстоянием и флагом равным нулю. Затем мы устанавливаем в ней флаг в 1 и проверяем все соседние с ней вершины. Если в ней расстояние больше, чем сумма расстояния до текущей вершины и длины ребра, то уменьшаем его. Цикл завершается когда флаги всех вершин становятся равны 1, либо когда у всех вершин c флагом 0 . Последний случай возможен тогда и только тогда, когда граф G не связан.

Доказательство правильности

Пусть l(v) - длина кратчайшего пути из вершины a в вершину v. Докажем по индукции, что в момент посещения любой вершины z, d(z)=l(z). База. Первой посещается вершина a. В этот момент d(a)=l(a)=0. Шаг. Пускай мы выбрали для посещения вершину . Докажем, что в этот момент d(z)=l(z). Для начала отметим, что для любой вершины v, всегда выполняется (алгоритм не может найти путь короче, чем кратчайший из всех существующих). Пусть P - кратчайший путь из a в z, y - первая непосещённая вершина на P, x - предшествующая ей (следовательно, посещённая). Поскольку путь P кратчайший, его часть, ведущая из a через x в y, тоже кратчайшая, следовательно l(y)=l(x)+w(xy). По предположению индукции, в момент посещения вершины x выполнялось d(x)=l(x), следовательно, вершина y тогда получила метку не больше чем d(x)+w(xy)=l(x)+w(xy)=l(y). Следовательно, d(y)=l(y). С другой стороны, поскольку сейчас мы выбрали вершину z, её метка минимальна среди непосещённых, то есть . Комбинируя это с , имеем d(z)=l(z), что и требовалось доказать.

Поскольку алгоритм заканчивает работу, когда все вершины посещены, в этот момент d=l для всех вершин.

Алгоримтм Демйкстры (Dijkstra"s algorithm) - алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях, например, его использует протокол OSPF для устранения кольцевых маршрутов. Известен также под названием "Сначала Кратчайший Путь" (Shortest Path First).

Алгоритм Дейкстры решает задачу о кратчайших путях из одной вершины для взвешенного ориентированного графа G = (V, E) с исходной вершиной s, в котором веса всех рёбер неотрицательны ((u, v) ? 0 для всех (u, v) E). В случае, когда ребра графа не равны, целесообразно использовать этот алгоритм.

Формулировка задачи. Имеется граф. Некоторая его вершина обозначена как вершина 1. Необходимо найти минимальные пути от вершины 1 до каждой из вершин графа. Минимальным путём будем называть путь с минимальной суммой цен вдоль пути. Ценой назовем неотрицательное число являющееся весом ребра.

Идея алгоритма. Идея основывается на следующем очевидном утверждении: Пусть построен минимальный путь из вершины а в вершину B. И пусть вершина B связана с некоторым количеством вершин i . Обозначим через C i - цену пути из вершины B в вершину i. Выберем из C i минимальную величину. Тогда минимальное продолжение пути из точки B пойдёт через выбранную величину.

Это утверждение действительно не требует доказательства. И из него вытекает очень серьёзное следствие. Пусть есть множество вершин через которые уже проходят минимальные пути. Такое множество гарантированно есть, это вершина 1. Утверждение сформулированное выше даёт возможность добавлять к уже существующему множеству вершин (будем далее называть их выделенными) еще одну вершину, а так как в графе количество вершин конечно, то за конечное количество шагов все вершины графа окажутся выделенными, а это и будет решением.

Сущность алгоритма Дейкстры и заключается в процедуре добавления еще одной вершины к множеству выделенных. Эта процедура состоит из двух шагов:

1. Строим множество вершин инцидентных выделенным и находим среди их вершину с наименьшей ценой. Найденная вершина добавляется в множество выделенных.

2. Строим множество вершин инцидентных выделенным и определяем для них новые цены. Новая цена вершины это минимальная цена пути от множества выделенных вершин до данной вершины. Строится новая цена так:

a. Для невыделенной вершины во множестве выделенных определяется подмножество вершин инцидентных данной.

b. Для каждой вершины выделенной подмножества определяется цена пути до данной.

c. Определяется минимальная цена. Эта цена и становится ценой вершины.

Алгоритм работает с двумя типами цен: ценой ребра и ценой вершины. Цены ребер являются постоянной величиной. Цены же вершин постоянно пересчитываются. Смысл этих цен различен. Цена ребра это цена перехода из вершины в вершину соединённую этим ребром. А цена вершины это цена минимального пути. Ещё одно важное замечание касается пересчета предварительных цен. Фактически, есть смысл пересчитывать предварительные цены только для тех вершин которые связаны с вершиной добавленной во множество выделенных на последнем шаге, так как для других вершин нет причин изменения предварительной цены.

Известно, что все цены (например, прокладки пути или проезда) неотрицательны. Найти наименьшую стоимость пути 1->i для всех i=1. n за время O (n2).

В процессе работы алгоритма некоторые города будут выделенными (в начале - только город 1, в конце - все). При этом:

для каждого выделенного города i хранится наименьшая стоимость пути 1->i; при этом известно, что минимум достигается на пути, проходящем только через выделенные города;

для каждого невыделенного города i хранится наименьшая стоимость пути 1->i, в котором в качестве промежуточных используются только выделенные города.

Множество выделенных городов расширяется на основании следующего замечания: если среди всех невыделенных городов взять тот, для которого хранимое число минимально, то это число является истинной наименьшей стоимостью. В самом деле, пусть есть более короткий путь. Рассмотрим первый невыделенный город на этом пути - уже до него путь длиннее! (Здесь существенна неотрицательность цен.)

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

Другими словами, каждой вершине из V сопоставим метку - минимальное известное расстояние от этой вершины до a. Алгоритм работает пошагово - на каждом шаге он "посещает" одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Инициализация. Метка самой вершины a полагается равной 0 , метки остальных вершин - бесконечности. Это отражает то, что расстояния от a до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Шаг алгоритма. Если все вершины посещены, алгоритм завершается. В противном случае из еще не посещенных вершин выбирается вершина u , имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Вершины, соединенные с вершиной u ребрами, назовем соседями этой вершины. Для каждого соседа рассмотрим новую длину пути, равную сумме текущей метки u и длины ребра, соединяющего u с этим соседом. Если полученная длина меньше метки соседа, заменим метку этой длиной. Рассмотрев всех соседей, пометим вершину u как посещенную и повторим шаг.

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

Опишем более подробно схему работы алгоритма Дейкстры.

Алгоритм использует три массива из N (= числу вершин сети) чисел каждый. Первый массив A содержит метки с двумя значения: 0 (вершина еще не рассмотрена) и 1 (вершина уже рассмотрена); второй массив B содержит расстояния - текущие кратчайшие рас - стояния от до соответствующей вершины; третий массив с содержит номера вершин - k-й элемент С [k] есть номер предпоследней вершины на текущем кратчайшем пути из Vi в Vk. Матрица расстояний D задает длины дуге D ; если такой дуги нет, то D присваивается большое число Б, равное "машинной бесконечности".

Теперь можно описать:

1. (инициализация). В цикле от 1 до N заполнить нулями массив A; заполнить числом i массив C; перенести i-ю строку матрицы D в массив B, A [i]: =1; C [i]: =0 (i - номер стартовой вершины)

2. (общий шаг). Hайти минимум среди неотмеченных (т.е. тех k, для которых A [k] =0); пусть минимум достигается на индексе j, т.е. B [j] <=B [k] Затем выполняются следующие операции: A [j]: =1; если B [k] >B [j] +D , то (B [k]: =B [j] +D ; C [k]: =j) (Условие означает, что путь Vi. Vk длиннее, чем путь Vi. Vj Vk). (Если все A [k] отмечены, то длина пути от Vi до Vk равна B [k]. Теперь надо) перечислить вершины, входящие в кратчайший путь).

3. (выдача ответа). (Путь от Vi до Vk выдается в обратном порядке следующей процедурой:)

2. Выдать z;

3. z: =C [z]. Если z = О, то конец, иначе перейти к 3.2.

Для выполнения алгоритма нужно N раз просмотреть массив B из N элементов, т.е. алгоритм Дейкстры имеет квадратичную сложность: O (n2).

Ниже приведена блок-схема алгоритма Дейкстры (см. рис.2).

Рис.2. Блок-схема алгоритма Дейкстры

В начале алгоритма расстояние для начальной вершины полагается равным нулю, а все остальные расстояния заполняются большим положительным числом (бомльшим максимального возможного пути в графе). Массив флагов заполняется нулями. Затем запускается основной цикл.

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

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

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

алгоритм Дейкстры ;
алгоритм Флойда ;
переборные алгоритмы.

Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется.

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

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

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

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

Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.

Шаг 2. Все вершины не выделены.

Шаг 3. Первая вершина объявляется текущей.

Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра , соединяющего текущую вершину с невыделенной.

Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход . Иначе, текущей становится найденная вершина . Она же выделяется.

Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.

Шаг 7. Переход на шаг 4.

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

Помимо указанных массивов будем использовать матрицу длин C , где элемент C – длина ребра (i,j) , если ребра нет, то ее длина полагается равной бесконечности, то есть больше любой фактической длины ребер. Фактически матрица C представляет собой матрицу смежности , в которой все нулевые элементы заменены на бесконечность.

Для определения самого

Алгоритм Дейкстры (англ. Dijkstra’s algorithm) - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса.

Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями - пути между ними (рёбра графа). В кружках обозначены номера вершин, над рёбрами обозначена их «цена» - длина пути. Рядом с каждой вершиной красным обозначена метка - длина кратчайшего пути в эту вершину из вершины 1.

Первый по очереди сосед вершины 1 - вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме значения метки вершины 1 и длины ребра, идущего из 1-й в 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2, бесконечности, поэтому новая метка 2-й вершины равна 7.

Аналогичную операцию проделываем с двумя другими соседями 1-й вершины - 3-й и 6-й.

Второй шаг . Шаг алгоритма повторяется. Снова находим «ближайшую» из непосещённых вершин. Это вершина 2 с меткой 7.

Первый (по порядку) сосед вершины 2 - вершина 1. Но она уже посещена, поэтому с 1-й вершиной ничего не делаем.

Следующий сосед вершины 2 - вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а это меньше 17, поэтому метка не меняется.

Ещё один сосед вершины 2 - вершина 4. Если идти в неё через 2-ю, то длина такого пути будет равна сумме кратчайшего расстояния до 2-й вершины и расстояния между вершинами 2 и 4, то есть 22 (7 + 15 = 22). Поскольку 22<, устанавливаем метку вершины 4 равной 22.

Все соседи вершины 2 просмотрены, замораживаем расстояние до неё и помечаем её как посещённую.

Третий шаг . Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим такие результаты:

Завершение выполнения алгоритма . Алгоритм заканчивает работу, когда нельзя больше обработать ни одной вершины. В данном примере все вершины зачёркнуты, однако ошибочно полагать, что так будет в любом примере - некоторые вершины могут остаться незачёркнутыми, если до них нельзя добраться, т. е. если граф несвязный. Результат работы алгоритма виден на последнем рисунке: кратчайший путь от вершины 1 до 2-й составляет 7, до 3-й - 9, до 4-й - 20, до 5-й - 20, до 6-й - 11.

Реализация алгоритма на различных языках программирования:

C++

#include "stdafx.h" #include using namespace std; const int V=6; //алгоритм Дейкстры void Dijkstra(int GR[V][V], int st) { int distance[V], count, index, i, u, m=st+1; bool visited[V]; for (i=0; i "< "<> "; cin>>start; Dijkstra(GR, start-1); system("pause>>void"); }

Pascal

program DijkstraAlgorithm; uses crt; const V=6; inf=100000; type vektor=array of integer; var start: integer; const GR: array of integer=((0, 1, 4, 0, 2, 0), (0, 0, 0, 9, 0, 0), (4, 0, 0, 7, 0, 0), (0, 9, 7, 0, 0, 2), (0, 0, 0, 0, 0, 8), (0, 0, 0, 0, 0, 0)); {алгоритм Дейкстры} procedure Dijkstra(GR: array of integer; st: integer); var count, index, i, u, m, min: integer; distance: vektor; visited: array of boolean; begin m:=st; for i:=1 to V do begin distance[i]:=inf; visited[i]:=false; end; distance:=0; for count:=1 to V-1 do begin min:=inf; for i:=1 to V do if (not visited[i]) and (distance[i]<=min) then begin min:=distance[i]; index:=i; end; u:=index; visited[u]:=true; for i:=1 to V do if (not visited[i]) and (GR<>0) and (distance[u]<>inf) and (distance[u]+GRinf then writeln(m," > ", i," = ", distance[i]) else writeln(m," > ", i," = ", "маршрут недоступен"); end; {основной блок программы} begin clrscr; write("Начальная вершина >> "); read(start); Dijkstra(GR, start); end.

Java

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.io.PrintWriter; import java.util.ArrayList; import java.util.Arrays; import java.util.StringTokenizer; public class Solution { private static int INF = Integer.MAX_VALUE / 2; private int n; //количество вершин в орграфе private int m; //количествое дуг в орграфе private ArrayList adj; //список смежности private ArrayList weight; //вес ребра в орграфе private boolean used; //массив для хранения информации о пройденных и не пройденных вершинах private int dist; //массив для хранения расстояния от стартовой вершины //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины private int pred; int start; //стартовая вершина, от которой ищется расстояние до всех других private BufferedReader cin; private PrintWriter cout; private StringTokenizer tokenizer; //процедура запуска алгоритма Дейкстры из стартовой вершины private void dejkstra(int s) { dist[s] = 0; //кратчайшее расстояние до стартовой вершины равно 0 for (int iter = 0; iter < n; ++iter) { int v = -1; int distV = INF; //выбираем вершину, кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } //рассматриваем все дуги, исходящие из найденной вершины for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int weightU = weight[v].get(i); //релаксация вершины if (dist[v] + weightU < dist[u]) { dist[u] = dist[v] + weightU; pred[u] = v; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used[v] = true; } } //процедура считывания входных данных с консоли private void readData() throws IOException { cin = new BufferedReader(new InputStreamReader(System.in)); cout = new PrintWriter(System.out); tokenizer = new StringTokenizer(cin.readLine()); n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа start = Integer.parseInt(tokenizer.nextToken()) - 1; //инициализируем списка смежности графа размерности n adj = new ArrayList[n]; for (int i = 0; i < n; ++i) { adj[i] = new ArrayList(); } //инициализация списка, в котором хранятся веса ребер weight = new ArrayList[n]; for (int i = 0; i < n; ++i) { weight[i] = new ArrayList(); } //считываем граф, заданный списком ребер for (int i = 0; i < m; ++i) { tokenizer = new StringTokenizer(cin.readLine()); int u = Integer.parseInt(tokenizer.nextToken()); int v = Integer.parseInt(tokenizer.nextToken()); int w = Integer.parseInt(tokenizer.nextToken()); u--; v--; adj[u].add(v); weight[u].add(w); } used = new boolean[n]; Arrays.fill(used, false); pred = new int[n]; Arrays.fill(pred, -1); dist = new int[n]; Arrays.fill(dist, INF); } //процедура восстановления кратчайшего пути по массиву предком void printWay(int v) { if (v == -1) { return; } printWay(pred[v]); cout.print((v + 1) + " "); } //процедура вывода данных в консоль private void printData() throws IOException { for (int v = 0; v < n; ++v) { if (dist[v] != INF) { cout.print(dist[v] + " "); } else { cout.print("-1 "); } } cout.println(); for (int v = 0; v < n; ++v) { cout.print((v + 1) + ": "); if (dist[v] != INF) { printWay(v); } cout.println(); } cin.close(); cout.close(); } private void run() throws IOException { readData(); dejkstra(start); printData(); cin.close(); cout.close(); } public static void main(String args) throws IOException { Solution solution = new Solution(); solution.run(); } }

Ещё один вариант:

Import java.io.*; import java.util.*; public class Dijkstra { private static final Graph.Edge GRAPH = { new Graph.Edge("a", "b", 7), new Graph.Edge("a", "c", 9), new Graph.Edge("a", "f", 14), new Graph.Edge("b", "c", 10), new Graph.Edge("b", "d", 15), new Graph.Edge("c", "d", 11), new Graph.Edge("c", "f", 2), new Graph.Edge("d", "e", 6), new Graph.Edge("e", "f", 9), }; private static final String START = "a"; private static final String END = "e"; public static void main(String args) { Graph g = new Graph(GRAPH); g.dijkstra(START); g.printPath(END); //g.printAllPaths(); } } class Graph { private final Map graph; // mapping of vertex names to Vertex objects, built from a set of Edges /** One edge of the graph (only used by Graph constructor) */ public static class Edge { public final String v1, v2; public final int dist; public Edge(String v1, String v2, int dist) { this.v1 = v1; this.v2 = v2; this.dist = dist; } } /** One vertex of the graph, complete with mappings to neighbouring vertices */ public static class Vertex implements Comparable { public final String name; public int dist = Integer.MAX_VALUE; // MAX_VALUE assumed to be infinity public Vertex previous = null; public final Map neighbours = new HashMap<>(); public Vertex(String name) { this.name = name; } private void printPath() { if (this == this.previous) { System.out.printf("%s", this.name); } else if (this.previous == null) { System.out.printf("%s(unreached)", this.name); } else { this.previous.printPath(); System.out.printf(" -> %s(%d)", this.name, this.dist); } } public int compareTo(Vertex other) { return Integer.compare(dist, other.dist); } } /** Builds a graph from a set of edges */ public Graph(Edge edges) { graph = new HashMap<>(edges.length); //one pass to find all vertices for (Edge e: edges) { if (!graph.containsKey(e.v1)) graph.put(e.v1, new Vertex(e.v1)); if (!graph.containsKey(e.v2)) graph.put(e.v2, new Vertex(e.v2)); } //another pass to set neighbouring vertices for (Edge e: edges) { graph.get(e.v1).neighbours.put(graph.get(e.v2), e.dist); //graph.get(e.v2).neighbours.put(graph.get(e.v1), e.dist); // also do this for an undirected graph } } /** Runs dijkstra using a specified source vertex */ public void dijkstra(String startName) { if (!graph.containsKey(startName)) { System.err.printf("Graph doesn"t contain start vertex \"%s\"\n", startName); return; } final Vertex source = graph.get(startName); NavigableSet q = new TreeSet<>(); // set-up vertices for (Vertex v: graph.values()) { v.previous = v == source ? source: null; v.dist = v == source ? 0: Integer.MAX_VALUE; q.add(v); } dijkstra(q); } /** Implementation of dijkstra"s algorithm using a binary heap. */ private void dijkstra(final NavigableSet q) { Vertex u, v; while (!q.isEmpty()) { u = q.pollFirst(); // vertex with shortest distance (first iteration will return source) if (u.dist == Integer.MAX_VALUE) break; // we can ignore u (and any other remaining vertices) since they are unreachable //look at distances to each neighbour for (Map.Entry a: u.neighbours.entrySet()) { v = a.getKey(); //the neighbour in this iteration final int alternateDist = u.dist + a.getValue(); if (alternateDist < v.dist) { // shorter path to neighbour found q.remove(v); v.dist = alternateDist; v.previous = u; q.add(v); } } } } /** Prints a path from the source to the specified vertex */ public void printPath(String endName) { if (!graph.containsKey(endName)) { System.err.printf("Graph doesn"t contain end vertex \"%s\"\n", endName); return; } graph.get(endName).printPath(); System.out.println(); } /** Prints the path from the source to every vertex (output order is not guaranteed) */ public void printAllPaths() { for (Vertex v: graph.values()) { v.printPath(); System.out.println(); } } }

C

#include #include #include //#define BIG_EXAMPLE typedef struct node_t node_t, *heap_t; typedef struct edge_t edge_t; struct edge_t { node_t *nd; /* target of this edge */ edge_t *sibling;/* for singly linked list */ int len; /* edge cost */ }; struct node_t { edge_t *edge; /* singly linked list of edges */ node_t *via; /* where previous node is in shortest path */ double dist; /* distance from origining node */ char name; /* the, er, name */ int heap_idx; /* link to heap position for updating distance */ }; /* --- edge management --- */ #ifdef BIG_EXAMPLE # define BLOCK_SIZE (1024 * 32 - 1) #else # define BLOCK_SIZE 15 #endif edge_t *edge_root = 0, *e_next = 0; /* Don"t mind the memory management stuff, they are besides the point. Pretend e_next = malloc(sizeof(edge_t)) */ void add_edge(node_t *a, node_t *b, double d) { if (e_next == edge_root) { edge_root = malloc(sizeof(edge_t) * (BLOCK_SIZE + 1)); edge_root.sibling = e_next; e_next = edge_root + BLOCK_SIZE; } --e_next; e_next->nd = b; e_next->len = d; e_next->sibling = a->edge; a->edge = e_next; } void free_edges() { for (; edge_root; edge_root = e_next) { e_next = edge_root.sibling; free(edge_root); } } /* --- priority queue stuff --- */ heap_t *heap; int heap_len; void set_dist(node_t *nd, node_t *via, double d) { int i, j; /* already knew better path */ if (nd->via && d >= nd->dist) return; /* find existing heap entry, or create a new one */ nd->dist = d; nd->via = via; i = nd->heap_idx; if (!i) i = ++heap_len; /* upheap */ for (; i > 1 && nd->dist < heap->dist; i = j) (heap[i] = heap[j])->heap_idx = i; heap[i] = nd; nd->heap_idx = i; } node_t * pop_queue() { node_t *nd, *tmp; int i, j; if (!heap_len) return 0; /* remove leading element, pull tail element there and downheap */ nd = heap; tmp = heap; for (i = 1; i < heap_len && (j = i * 2) <= heap_len; i = j) { if (j < heap_len && heap[j]->dist > heap->dist) j++; if (heap[j]->dist >= tmp->dist) break; (heap[i] = heap[j])->heap_idx = i; } heap[i] = tmp; tmp->heap_idx = i; return nd; } /* --- Dijkstra stuff; unreachable nodes will never make into the queue --- */ void calc_all(node_t *start) { node_t *lead; edge_t *e; set_dist(start, start, 0); while ((lead = pop_queue())) for (e = lead->edge; e; e = e->sibling) set_dist(e->nd, lead, lead->dist + e->len); } void show_path(node_t *nd) { if (nd->via == nd) printf("%s", nd->name); else if (!nd->via) printf("%s(unreached)", nd->name); else { show_path(nd->via); printf("-> %s(%g) ", nd->name, nd->dist); } } int main(void) { #ifndef BIG_EXAMPLE int i; # define N_NODES ("f" - "a" + 1) node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%c", "a" + i); # define E(a, b, c) add_edge(nodes + (a - "a"), nodes + (b - "a"), c) E("a", "b", 7); E("a", "c", 9); E("a", "f", 14); E("b", "c", 10);E("b", "d", 15);E("c", "d", 11); E("c", "f", 2); E("d", "e", 6); E("e", "f", 9); # undef E #else /* BIG_EXAMPLE */ int i, j, c; # define N_NODES 4000 node_t *nodes = calloc(sizeof(node_t), N_NODES); for (i = 0; i < N_NODES; i++) sprintf(nodes[i].name, "%d", i + 1); /* given any pair of nodes, there"s about 50% chance they are not connected; if connected, the cost is randomly chosen between 0 and 49 (inclusive! see output for consequences) */ for (i = 0; i < N_NODES; i++) { for (j = 0; j < N_NODES; j++) { /* majority of runtime is actually spent here */ if (i == j) continue; c = rand() % 100; if (c < 50) continue; add_edge(nodes + i, nodes + j, c - 50); } } #endif heap = calloc(sizeof(heap_t), N_NODES + 1); heap_len = 0; calc_all(nodes); for (i = 0; i < N_NODES; i++) { show_path(nodes + i); putchar("\n"); } #if 0 /* real programmers don"t free memories (they use Fortran) */ free_edges(); free(heap); free(nodes); #endif return 0; }

PHP

$edge, "cost" => $edge); $neighbours[$edge] = array("end" => $edge, "cost" => $edge); } $vertices = array_unique($vertices); foreach ($vertices as $vertex) { $dist[$vertex] = INF; $previous[$vertex] = NULL; } $dist[$source] = 0; $Q = $vertices; while (count($Q) > 0) { // TODO - Find faster way to get minimum $min = INF; foreach ($Q as $vertex){ if ($dist[$vertex] < $min) { $min = $dist[$vertex]; $u = $vertex; } } $Q = array_diff($Q, array($u)); if ($dist[$u] == INF or $u == $target) { break; } if (isset($neighbours[$u])) { foreach ($neighbours[$u] as $arr) { $alt = $dist[$u] + $arr["cost"]; if ($alt < $dist[$arr["end"]]) { $dist[$arr["end"]] = $alt; $previous[$arr["end"]] = $u; } } } } $path = array(); $u = $target; while (isset($previous[$u])) { array_unshift($path, $u); $u = $previous[$u]; } array_unshift($path, $u); return $path; } $graph_array = array(array("a", "b", 7), array("a", "c", 9), array("a", "f", 14), array("b", "c", 10), array("b", "d", 15), array("c", "d", 11), array("c", "f", 2), array("d", "e", 6), array("e", "f", 9)); $path = dijkstra($graph_array, "a", "e"); echo "path is: ".implode(", ", $path)."\n";

Python

from collections import namedtuple, queue from pprint import pprint as pp inf = float("inf") Edge = namedtuple("Edge", "start, end, cost") class Graph(): def __init__(self, edges): self.edges = edges2 = self.vertices = set(sum(( for e in edges2), )) def dijkstra(self, source, dest): assert source in self.vertices dist = {vertex: inf for vertex in self.vertices} previous = {vertex: None for vertex in self.vertices} dist = 0 q = self.vertices.copy() neighbours = {vertex: set() for vertex in self.vertices} for start, end, cost in self.edges: neighbours.add((end, cost)) #pp(neighbours) while q: u = min(q, key=lambda vertex: dist) q.remove(u) if dist[u] == inf or u == dest: break for v, cost in neighbours[u]: alt = dist[u] + cost if alt < dist[v]: # Relax (u,v,a) dist[v] = alt previous[v] = u #pp(previous) s, u = deque(), dest while previous[u]: s.pushleft(u) u = previous[u] s.pushleft(u) return s graph = Graph([("a", "b", 7), ("a", "c", 9), ("a", "f", 14), ("b", "c", 10), ("b", "d", 15), ("c", "d", 11), ("c", "f", 2), ("d", "e", 6), ("e", "f", 9)]) pp(graph.dijkstra("a", "e")) Output: ["a", "c", "d", "e"]