Алгори́тм Де́йкстры (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 для всех вершин.

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.

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

Для начала рассмотрим алгоритм Фалкерсона (графический способ упорядочивания элементов):

• 1. Найти вершины графа, в которые не входит не одна дуга. Они образуют первую группу. Пронумеровать вершины группы в произвольном порядке.
• 2. Вычеркнуть все пронумерованные вершины и дуги, из них исходящие. В получившемся графе найдется, по крайней мере, одна вершина, в которую не входит ни одна дуга. Этой вершине, входящей во вторую группу, присвоить очередной номер, и т. д. Второй шаг повторять до тех пор, пока не будут упорядочены все вершины.

Теперь рассмотрим алгоритм нахождения кратчайшего пути между двумя заданными вершинами в ориентированном графе. Пусть G = {S, U, ? } - ориентированный граф со взвешенными дугами. Обозначим s-вершину - начало пути и t-вершину - конец пути.

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

Этап 1. Нахождение кратчайшего пути.

Шаг 1. Присвоение вершинам начальных меток.

Полагаем d(s)=0* и считаем эту метку постоянной (постоянные метки помечаются сверху звёздочкой). Для остальных вершин x i S, x i ?s полагаем d(x i) = ? и считаем эти метки верными. Пусть x” = s, x” - обозначение текущей вершины.

Шаг 2. Изменение меток.

Для каждой вершины x i с временной меткой, непосредственно следующей за вершиной x”, меняем ее метку в соответствии со следующим правилом:

d нов. (x i) = min{d стар. (x i), d(x”)+щ(x”, x i)}.(1. 6. 1)

Шаг 3. Превращение метки из временной в постоянную.

Из всех вершин с временными метками выбираем вершину x j * с наименьшим значением метки

d(x j *) = min {d(x j) / x j S, d(x j) - временная}. (1. 6. 2)

Превращаем эту метку в постоянную и полагаем x” = x j *.

Шаг 4. Проверка на завершение первого этапа.

Если x” = t, то d(x”) - длина кратчайшего пути от s до t. В противном случае происходит возвращение ко второму шагу.

Этап 2. Построение кратчайшего пути.

Шаг 5. Последовательный поиск дуг кратчайшего пути.

Среди вершин, непосредственно предшествующих вершине x” c постоянными метками, находим вершину x i , удовлетворяющую соотношению

d(x”) = d(x i) + щ(x i , x”).(1. 6. 3)

Включаем дугу (x i , x”) в искомый путь и полагаем x” = x i .

Шаг 6. Проверка на завершение второго этапа.

Если x” = s, то кратчайший путь найден - его образует последовательность дуг, полученных на пятом шаге и выстроенных в обратном порядке. В противном случае возвращаемся к пятому шагу.

Пример 8: Задана весовая матрица? графа G. Найти минимальный путь из вершины x 1 в вершину x6 по алгоритму Дейкстры.

На рисунке 1. 11 изображён сам граф по данной матрице весов. Поскольку на данном графе есть цикл между вершинами x 2 , x 3 и x 5 , то вершины графа нельзя упорядочить по алгоритму Фалкерсона. На рисунке графа временные и постоянные метки указаны над соответствующей вершиной. Итак, распишем подробно работу алгоритма Дейкстры по шагам.

Шаг 1. Полагаем d(x 1) = 0*, x” = x 1 , d(x 2) = d(x 3) = d(x 4) = d(x 5) = d(x 6) = ?.

1-ая итерация.

Шаг 2. Множество вершин, непосредственно следующих за x” = x1 со временными метками S” = {x 2 , x 4 , x 5 }. Пересчитываем временные метки вершин: d(x 2) = min{?, 0*, + 9} = 9, d(x 4) = min{?, 0* + 6} = 6, d(x 5) = min{?, 0* + 11} = 11.

Шаг 3. Одна из временных меток превращается в постоянную min{9, ?, 6, 11, ?} = 6* = d(x 4), x” = x 4 .

Шаг 4. x” = x 4 ? t = x 6 , происходит возвращение на второй шаг.

2-ая итерация.

Шаг 2. S” = {x 2 , x 3 , x 5 }, d(x 2) = min{9, 6* + 5} = 9, d(x 3) = min {?, 6* + 7} = 13, d(x 5) = min{11, 6* + 6} = 11.

Шаг 3. min{d(x 2), d(x 3), d(x 5), d(x 6)} = min{9, 13, 11, ?} = 9* = d(x 2), x” = x 2 .

Шаг 4. x 2 ? x 6 , возвращение на второй шаг.

3-я итерация.

Шаг 2. S” ={x 3 }, d(x 3) = min{13, 9* + 8} = 13.

Шаг 3. min{d(x 3), d(x 5), d(x 6)} = min{31, 11, ?} = 11* = d(x 5), x” = x 5 .

Шаг 4. x 5 ? x 6 , возвращение на второй шаг.

4-ая итерация.

Шаг 2. S”={x 6 }, d(x 6) = min{?, 11* + 4} = 15.

Шаг 3. min {d(x 3), d(x 6)} = min{13, 15} = 13* = d(x 3), x” = x 3 .

Шаг 4. x 3 ? x 6 , возвращение на второй шаг.

5-ая итерация.

Шаг 2. S” = {x 6 }, d(x 6) = min{15, 13* + 9} = 15.

Шаг 3. min{d(x 6) } = min{15} = 15*, x” = x 6 .

Шаг 4. x 6 = t = x 6 , конец первого этапа.

Шаг 5. Составим множество вершин, непосредственно предшествующих x” = x 6 с постоянными метками S” = {x 3 , x 5 }. Проверим для этих двух вершин выполнение равенства d нов. (x i) = min{d стар. (x i), d(x”) + щ(x”, x i)}:

d(x”) = 15 = 11* + 4 = d(x 5) + щ(x 5 , x 6),

d(x”) = 15 ? 13* + 9 = d(x 3) + щ(x 3 , x 6).

Включаем дугу (x 5 , x 6) в кратчайший путь. x” = x 5 .

Шаг 6. x” ? s = x 1 , возвращение на пятый шаг.

2-ая итерация.

Шаг 5. S” = {x 1 , x 4 }.

d(x”) = 11 = 0* + 11 = d(x 1) + щ(x 1 , x 5),

d(x”) = 11 ? 6* + 6 = d(x 4) + щ(x 4 , x 5).

Включаем дугу (x 1 , x 5) в кратчайший путь. x” = x 1 .

Шаг 6. x” = s = x 1 , завершение второго этапа.

Итак, кратчайший путь от вершины x 1 до вершины x 6 построен. Его длина (вес) равна 15, сам путь образует следующая последовательность дуг: м = (x 1 , x 5) - (x 5 , x 6).

) выполняется за время O(m + n \ln n) и является асимптотически быстрейшим из известных последовательных алгоритмов для данного класса задач.

1.2 Математическое описание алгоритма

Пусть задан граф G = (V, E) с весами рёбер f(e) и выделенной вершиной-источником u . Обозначим через d(v) кратчайшее расстояние от источника u до вершины v .

Пусть уже вычислены все расстояния, не превосходящие некоторого числа r , то есть расстояния до вершин из множества V_r = \{ v \in V \mid d(v) \le r \} . Пусть

(v, w) \in \arg\min \{ d(v) + f(e) \mid v \in V, e = (v, w) \in E \}.

Тогда d(w) = d(v) + f(e) , и v лежит на кратчайшем пути от u к w .

Величины d^+(w) = d(v) + f(e) , где v \in V_r , e = (v, w) \in E , называются предполагаемыми расстояниями и являются оценкой сверху для настоящих расстояний: d(w) \le d^+(w) .

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

1.3 Вычислительное ядро алгоритма

Основные вычисления связаны с операциями над очередью с приоритетом:

• извлечение минимального элемента (delete_min);
• уменьшение приоритета элемента (decrease_key).

1.4 Макроструктура алгоритма

Псевдокод алгоритма:

Входные данные : граф с вершинами V , рёбрами E с весами f (e ); вершина-источник u . Выходные данные : расстояния d (v ) до каждой вершины v ∈ V от вершины u . Q := new priority queue for each v ∈ V : if v = u then d (v ) := 0 else d (v ) := ∞ Q .insert(v , d (v )) while Q ≠ ∅: v := Q .delete_min() for each e = (v , w ) ∈ E : if d (w ) > d (v ) + f (e ): d (w ) := d (v ) + f (e ) Q .decrease_key(w , d (w ))

1.5 Схема реализации последовательного алгоритма

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

Возможен вариант реализации, когда вершины добавляются в очередь не на этапе инициализации, а в момент первого посещения.

1.6 Последовательная сложность алгоритма

Последовательная сложность алгоритма равна O(C_1 m + C_2n) , где

• C_1 – количество операций уменьшения расстояния до вершины;
• C_2 – количество операций вычисления минимума.

Оригинальный алгоритм Дейкстры использовал в качестве внутренней структуры данных списки, для которых C_1 = O(1) , C_2 = O(n) , так что общая сложность составляла O(n^2) .

При использовании фибоначчиевой кучи время вычисления минимума сокращается до C_2 = O(\ln n) , так что общая сложность равна O(m + n \ln n) , что является асимптотически наилучшим известным результатом для данного класса задач.

1.7 Информационный граф

Приводится граф алгоритма для базовой реализации алгоритма Дейкстры на списках или массивах.

Рисунок 1. Граф алгоритма без отображения входных и выходных данных. n=3. Желтым цветом обозначены операции сравнения, зеленым - операции изменения меток вершин, синим - пометка вершины.

1.8 Ресурс параллелизма алгоритма

Алгоритм Дейкстры допускает эффективную параллелизацию , среднее время работы O(n^{1/3}\ln n) с объёмом вычислений O(n \ln n + m) .

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

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

Рисунок 6. Сравнение значений оценки daps

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

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

Рисунок 7. Сравнение значений оценки cvg

2.3 Возможные способы и особенности параллельной реализации алгоритма

2.4 Масштабируемость алгоритма и его реализации

2.4.1 Масштабируемость алгоритма

2.4.2 Масштабируемость реализации алгоритма

Проведём исследование масштабируемости параллельной реализации алгоритма согласно методике . Исследование проводилось на суперкомпьютере "Ломоносов" Суперкомпьютерного комплекса Московского университета . Набор и границы значений изменяемых параметров запуска реализации алгоритма:

• число процессоров со значениями квадрата целого числа;
• размер графа с шагом 16000.

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

Рисунок 8. Параллельная реализация алгоритма. Изменение производительности в зависимости от числа процессоров и размера области.

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

2.5 Динамические характеристики и эффективность реализации алгоритма

Для проведения экспериментов использовалась реализация алгоритма Дейкстры. Все результаты получены на суперкомпьютере "Ломоносов". Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор intel 13.1.0. На рисунках показана эффективность реализации алгоритма Дейкстры на 32 процессах.

Рисунок 9. График загрузки CPU при выполнении алгоритма Дейкстры

На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 50%. Это указывает на равномерную загруженность вычислениями процессоров, при использовании 8 процессов на вычислительный узел и без использования Hyper Threading.

Рисунок 10. График операций с плавающей точкой в секунду при выполнении алгоритма Дейкстры

На Рисунке 10 показан график количества операций с плавающей точкой в секунду. На графике видна общая очень низкая производительность вычислений около 250 Kфлопс в пике и около 150 Кфлопс в среднем по всем узлам. Это указывает то, что в программе почти все вычисления производятся с целыми числами.

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

Рисунок 15. График скорости передачи по сети Infiniband в байт/сек при работе алгоритма Дейкстры

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

Рисунок 16. График скорости передачи по сети Infiniband в пакетах/сек при работе алгоритма Дейкстры

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

Рисунок 17. График числа процессов, ожидающих вхождения в стадию счета (Loadavg), при работе алгоритма Дейкстры

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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