Алгоритм Дейкстры позволяет найти кратчайший путь между двумя любыми вершинами графа (или кратчайший путь сети между заданным исходным и любым другим узлом).
Граф — это совокупность двух множеств: точек (называются вершинами) и путей между ними (изображаются линиями и называются рёбрами).
Алгоритм Дейкстры применяется в жизни. Например, можно использовать графы для моделирования транспортной сети, где точки (вершины) являются объектами, которые отправляют или получают посылки/продукты (места, что водитель должен посетить), а рёбра (линии) представляют собой соединяющие их дороги:
Графы могут быть двух типов:
Пример
Рассмотрим представленный выше пример:
Алгоритм произведёт кратчайший путь от узла 0 ко всем остальным узлам графа.
Для этого графа мы будем предполагать, что вес рёбер (вес или стоимость всегда являются неотрицательными, т.е. ≥ 0; это цифра возле каждой линии) представляет собой расстояние между двумя узлами:
Мы найдём кратчайший путь от узла 0 к узлу 1, потом к узлу 2, потом к узлу 3 и т. д. для каждого узла в графе.
Этот граф также можно представить в виде матрицы:
0
1
2
3
4
0
0
7
5
1
7
0
3
5
2
5
3
0
4
3
5
0
6
Таблица: слева «выходит из», сверху «куда направляется», и выставляем «вес» (пример: из «0» идёт в «1» с весом «7», из «0» идёт в «2» с весом «5», и больше из 0 не выходит ничего).
Если можно идти из одного узла в другой и обратно, это указывается в матрице (например: из 2 в 1 с весом 3 И из 1 в 2 с весом 3).
Пошаговый процесс нахождения минимального пути
Шаг 0. В этом примере исходным узлом будет узел 0 (т.к. расстояние от исходного узла до самого себя равно 0; но исходным узлом может быть любой узел, который вы выберете).
Шаг 1. Для первоначального представления расстояния от исходного узла до всех остальных узлов мы используем символ бесконечности, т.к. оно ещё не определено:
Делаем такой список узлов с расстояниями:
Расстояние:
Мы начали с узла 0, значит, отмечаем этот узел как посещённый на диаграмме и вычёркиваем его из списка непосещённых узлов (дистанцию, которая равна нулю, уже обозначили).
Шаг 2. Теперь проверяем расстояние от узла 0 до соседних с ним узлов. Как это видно на картинке, это узлы 1 и 2 (см. красные линии), это наши возможные пути:
Путь 1 = 7, путь 2 = 5, т.к. путь 2 короче (дешевле), то выберем его.
Рассматриваем дальнейшие пути/узлы:
Однако существует прямой путь из 0 в узел 1, который равняется 7, а 7
Остались непосещёнными 3 и 4.
Непосещённый сосед 2 – это 4 (мы его ещё не посетили, мы только посчитали), в него можно попасть 5 + 4 = 9, ставим 9.
Непосещённый сосед 1 – это 3, в него можно попасть через:
Естественно выбираем самый короткий путь (равный 12).
Путь 4 тоже оставляем тот, который был выбран, т.к. более короткого не видно (путь через 3 равен 12 + 6 = 18), ставим его посещённым.
Так как непосещённых узлов нет, всё готово!
Расстояние:
Минимальное расстояние каждого узла, что мы нашли, представляет собой минимальное расстояние от этого узла до узла 0 (мы его выбрали в начале в качестве начального узла).
Минимальное остовное дерево
Ещё существует метод «Минимальное остовное дерево», и эти процессы часто путаются. Однако алгоритм Дейкстры отличается от метода Минимального остовного дерева тем, что кратчайшее расстояние между двумя вершинами может не включать все вершины графа; т.е. в алгоритме Дейкстры все вершины должны быть посещены.
Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе
Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.
Для примера возьмем такой ориентированный граф G:
Этот граф мы можем представить в виде матрицы С:
Возьмем в качестве источника вершину 1. Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5. Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере.
Присвоим 1-й вершине метку равную 0, потому как эта вершина — источник. Остальным вершинам присвоим метки равные бесконечности.
Далее выберем такую вершину W, которая имеет минимальную метку (сейчас это вершина 1) и рассмотрим все вершины в которые из вершины W есть путь, не содержащий вершин посредников. Каждой из рассмотренных вершин назначим метку равную сумме метки W и длинны пути из W в рассматриваемую вершину, но только в том случае, если полученная сумма будет меньше предыдущего значения метки. Если же сумма не будет меньше, то оставляем предыдущую метку без изменений.
После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещённую, и выбираем из ещё не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W.
Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.
Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины.
Выполнив все действия получим такой результат:
Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = <1, 1, 1, 1, 1>). Далее на этапе пересчета значения метки для рассматриваемой вершины, в случае если метка рассматриваемой вершины меняется на меньшую, в массив Р мы записываем значение текущей вершины W. Например: у 3-ей вершины была метка со значением «30», при W=1. Далее при W=5, метка 3-ей вершины изменилась на «20», следовательно мы запишем значение в вектор Р — Р[3]=5. Также при W=5 изменилось значение метки у 4-й вершины (было «50», стало «40»), значит нужно присвоить 4-му элементу вектора Р значение W — P[4]=5. В результате получим вектор Р = <1, 1, 5, 5, 1>.
Зная что в каждом элементе вектора Р записана последняя промежуточная вершина на пути между источником и конечной вершиной, мы можем получить и сам кратчайший маршрут.
Рассмотрим пример нахождение кратчайшего пути. Дана сеть автомобильных дорог, соединяющих области города. Некоторые дороги односторонние. Найти кратчайшие пути от центра города до каждого города области.
Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.
Инициализация
Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.
Первый шаг
Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.
Первый сосед вершины 1 – вершина 2, потому что длина пути до неё минимальна. Длина пути в неё через вершину 1 равна сумме кратчайшего расстояния до вершины 1 (значению её метки) и длины ребра, идущего из 1-й во 2-ю, то есть 0 + 7 = 7. Это меньше текущей метки вершины 2 (10000), поэтому новая метка 2-й вершины равна 7. Аналогично находим длины пути для всех других соседей (вершины 3 и 6).
Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.
Второй шаг
Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.
Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.
Вершина 1 уже посещена. Следующий сосед вершины 2 — вершина 3, так как имеет минимальную метку из вершин, отмеченных как не посещённые. Если идти в неё через 2, то длина такого пути будет равна 17 (7 + 10 = 17). Но текущая метка третьей вершины равна 9, а 9 Реализация на C++
Алгоритм Дейкстры позволяет нам найти кратчайший путь между любыми двумя вершинами графа.
Он отличается от минимального остовного дерева тем, что кратчайшее расстояние между двумя вершинами может не включать все вершины графа.
Как работает алгоритм Дейкстры
Дейкстра использовал это свойство в противоположном направлении, т.е. мы переоцениваем расстояние каждой вершины от начальной вершины. Затем мы посещаем каждый узел и его соседей, чтобы найти кратчайший подпуть к этим соседям.
Алгоритм использует «жадный» подход в том смысле, что мы находим следующее лучшее решение, надеясь, что конечный результат является лучшим решением для всей задачи.
Пример алгоритма Дейкстры
Проще начать с примера, а затем подумать об алгоритме.
Алгоритм Дейкстры. Псевдокод.
Нам также хотелось бы получить кратчайший путь, а не только знать его длину. Для этого мы сопоставляем каждую вершину с последней обновленной длиной пути.
Как только алгоритм закончен, мы можем вернуться от вершины назначения к исходной вершине, чтобы найти путь.
Очередь с минимальным приоритетом может использоваться для эффективного получения вершины с наименьшим расстоянием пути.
Код для алгоритма Дейкстры
Реализация алгоритма Дейкстры в C ++ приведена ниже. Сложность кода может быть улучшена, но абстракции удобны для связи кода с алгоритмом.
Алгоритм Дейкстры [1] предназначен для решения задачи поиска кратчайшего пути на графе. Для заданного ориентированного взвешенного графа с неотрицательными весами алгоритм находит кратчайшие расстояния от выделенной вершины-источника до всех остальных вершин графа. Алгоритм Дейкстры (с использованием фибоначчиевой кучи [2] ) выполняется за время [math]O(m + n \ln n)[/math] и является асимптотически быстрейшим из известных последовательных алгоритмов для данного класса задач.
1.2 Математическое описание алгоритма
Алгоритм Дейкстры на каждом шаге находит вершину с наименьшим предполагаемым расстоянием, помечает её как посещённую и обновляет предполагаемые расстояния для всех концов рёбер, исходящих из неё.
1.3 Вычислительное ядро алгоритма
Основные вычисления связаны с операциями над очередью с приоритетом:
1.4 Макроструктура алгоритма
1.5 Схема реализации последовательного алгоритма
Возможен вариант реализации, когда вершины добавляются в очередь не на этапе инициализации, а в момент первого посещения.
1.6 Последовательная сложность алгоритма
1.7 Информационный граф
Приводится граф алгоритма для базовой реализации алгоритма Дейкстры на списках или массивах.
1.8 Ресурс параллелизма алгоритма
Алгоритм Δ-шагания может рассматриваться как параллельная версия алгоритма Дейкстры.
1.9 Входные и выходные данные алгоритма
Выходные данные (возможные варианты):
1.10 Свойства алгоритма
2 Программная реализация алгоритма
2.1 Особенности реализации последовательного алгоритма
2.2 Локальность данных и вычислений
2.2.1 Локальность реализации алгоритма
2.2.1.1 Структура обращений в память и качественная оценка локальности
На рис. 1 представлен профиль обращений в память для реализации алгоритма Дейкстры. Первое, что бросается в глаза, – большая разрозненность обращений. В частности, значительные области выше и ниже фрагмента 2 остаются пустыми, при этом сами обращения объединены лишь в небольшие группы. Это говорит о низкой эффективности, поскольку: а) повторные обращения практически отсутствуют либо происходят через значительный промежуток времени; б) расстояния между идущими подряд обращениями может быть очень большим.
Однако при ближайшем рассмотрении может оказаться, что такие участки обладают высокой локальностью и состоят из значительного числа обращений. Более того, на общем профиле есть несколько областей (фрагменты 1 и 2), в которых обращения хорошо локализованы. Необходимо исследовать отдельные участки более подробно.
Перейдем к изучению фрагмента 1 (рис. 2), в рамках которого выполняются обращения к двум небольшим массивам. Можно увидеть, что здесь задействованы только примерно 500 элементов, при этом к ним выполняется около 100 тысяч обращений. Весь профиль составляет около 120 тысяч обращений, поэтому получается, что подавляющая их часть выполняется именно к этим элементам.
Поскольку число элементов невелико, локальность в данном случае заведомо будет достаточно высокой, независимо от структуры самого фрагмента. Однако на рис. 3, где представлены два участка из фрагмента 1, можно увидеть, что фрагмент в основном состоит из последовательных переборов, при этом данные зачастую задействованы повторно через не очень большие промежутки. Все это позволяет говорить, что данный фрагмент обладает высокой как пространственной, так и временной локальностью.
Рассмотрим теперь более подробно фрагмент 2 (рис. 4), в рамках которого выполняются обращения к еще служебному массиву. Здесь профиль состоит из двух этапов. На первом заметен достаточно хаотичный разброс обращений, напоминающий случайный доступ. На втором обращения образуют подобие последовательного перебора. В целом такой профиль характеризуется очень низкой временной локальностью (повторные обращения практически или полностью отсутствуют) и достаточно низкой пространственной локальностью (из-за случайного доступа на первом этапе).
Заметим, что при этом число задействованных элементов здесь больше, чем во фрагменте 1, однако число обращений гораздо меньше.
Далее остаются для рассмотрения два массива (область между фрагментами 1 и 2 и область ниже фрагмента 2). Характер обращений к этим массивам во многом похож, поэтому достаточно изучить более подробно только один из них.
Фрагмент 3 рассмотрен на рис. 5. Этот участок отражаeт достаточно большую область, что не позволяет проанализировать профиль вплоть до отдельных обращений, однако здесь этого и не требуется. Из данного фрагмента видно, что основу профиля составляют участки с последовательным (или с небольшим шагом) перебором, состоящие из небольшого числа элементов – выделенный желтым самый большой участок фрагмента состоит всего из пары сотен обращений. При этом между разными участками расстояние может быть существенным. Все это говорит об очень низкой локальности (как пространственной, так и временной) в случае двух рассматриваемых массивов.
В целом, несмотря на положительный вклад массивов из фрагмента 1, локальность общего профиля должна быть достаточно низкой, вследствие неэффективного использования данных в остальной части профиля.
2.2.1.2 Количественная оценка локальности
Основной фрагмент реализации, на основе которого были получены количественные оценки, приведен здесь (функция Kernel). Условия запуска описаны здесь.
Первая оценка выполняется на основе характеристики daps, которая оценивает число выполненных обращений (чтений и записей) в память в секунду. Данная характеристика является аналогом оценки flops применительно к работе с памятью и является в большей степени оценкой производительности взаимодействия с памятью, чем оценкой локальности. Однако она служит хорошим источником информации, в том числе для сравнения с результатами по следующей характеристике cvg.
На рисунке 6 приведены значения daps для реализаций распространенных алгоритмов, отсортированные по возрастанию (чем больше daps, тем в общем случае выше производительность). Можно увидеть, что производительность работы с памятью достаточно низка. Это неудивительно, поскольку реализации алгоритмов над графами почти всегда обладают низкой эффективностью вследствие нерегулярности доступа к данным, что мы и увидели при анализе профиля обращений.
Вторая характеристика – cvg – предназначена для получения более машинно-независимой оценки локальности. Она определяет, насколько часто в программе необходимо подтягивать данные в кэш-память. Соответственно, чем меньше значение cvg, тем реже это нужно делать, тем лучше локальность.
На рисунке 7 приведены значения cvg для того же набора реализаций, отсортированные по убыванию (чем меньше cvg, тем в общем случае выше локальность). Можно увидеть, что в данном случае значение cvg хорошо коррелирует с оценкой производительности и отражает низкую локальность, что соответствует выводам, сделанным при качественной оценке локальности.
2.3 Возможные способы и особенности параллельной реализации алгоритма
2.4 Масштабируемость алгоритма и его реализации
2.4.1 Масштабируемость алгоритма
2.4.2 Масштабируемость реализации алгоритма
Проведём исследование масштабируемости параллельной реализации алгоритма согласно методике. Исследование проводилось на суперкомпьютере «Ломоносов» [4] Суперкомпьютерного комплекса Московского университета. Набор и границы значений изменяемых параметров запуска реализации алгоритма:
На следующем рисунке приведен график производительности выбранной реализации алгоритма в зависимости от изменяемых параметров запуска.
В силу особенностей параллельной реализации алгоритма производительность в целом достаточно низкая и с ростом числа процессов увеличивается медленно, а при приближении к числу процессов 128 начинает уменьшаться. Это объясняется использованием коллективных операций на каждой итерации алгоритма и тем, что затраты на коммуникационные обмены существенно возрастают с ростом числа использованных процессов. Вычисления на каждом процессе проходят достаточно быстро и потому декомпозиция графа слабо компенсирует эффект от затрат на коммуникационные обмены.
2.5 Динамические характеристики и эффективность реализации алгоритма
Для проведения экспериментов использовалась реализация алгоритма Дейкстры. Все результаты получены на суперкомпьютере «Ломоносов». Использовались процессоры Intel Xeon X5570 с пиковой производительностью в 94 Гфлопс, а также компилятор intel 13.1.0. На рисунках показана эффективность реализации алгоритма Дейкстры на 32 процессах.
На графике загрузки процессора видно, что почти все время работы программы уровень загрузки составляет около 50%. Это указывает на равномерную загруженность вычислениями процессоров, при использовании 8 процессов на вычислительный узел и без использования Hyper Threading.
На Рисунке 10 показан график количества операций с плавающей точкой в секунду. На графике видна общая очень низкая производительность вычислений около 250 Kфлопс в пике и около 150 Кфлопс в среднем по всем узлам. Это указывает то, что в программе почти все вычисления производятся с целыми числами.
На графике кэш-промахов первого уровня видно, что число промахов очень большое для нескольких ядер и находится на уровне 15 млн/сек (в пике до 60 млн/сек), что указывает на интенсивные вычисления в части процессов. В среднем по всем узлам значения значительно ниже (около 9 млн/сек). Это указывает на неравномерное распределение вычислений.
На графике кэш-промахов третьего уровня видно, что число промахов очень невелико и находится на уровне 1,2 млн/сек, однако в среднем по всем узлам значения около 0,5 млн/сек. Соотношение кэш промахов L1|L3 для процессов с высокой производительностью доходит до 60, однако в среднем около 30. Это указывает на очень хорошую локальность вычислений как у части процессов, так и для всех в среднем, и это является признаком высокой производительности.
На графике обращений в память видна достаточно типичная картина для таких приложений. Активность чтения достаточно низкая, что в совокупности с низкими значениями кэш-промахов L3 указывает на хорошую локальность. Хорошая локальность приложения также указывает на то, что значение около 1 млн/сек для задачи является результатом высокой производительности вычислений, хотя и присутствует неравномерность между процессами.
На графике записей в память видна похожая картина неравномерности вычислений, при которой одновременно активно выполняют запись только несколько процессов. Это коррелирует с другими графиками выполнения. Стоит отметить достаточно низкое число обращений на запись в память. Это указывает на хорошую организацию вычислений и достаточно эффективную работу с памятью.
На графике скорости передачи данных по сети Infiniband наблюдается достаточно высокая скорость передачи данных в байтах в секунду. Это говорит о том, что процессы между собой обмениваются интенсивно и вероятно достаточно малыми порциями данных, потому как производительность вычислений высока. Стоит отметить, что скорость передачи отличается между процессами, что указывает на дисбаланс вычислений.
На графике скорости передачи данных в пакетах в секунду наблюдается крайне высокая интенсивность передачи данных. Это говорит о том, что, вероятно, процессы обмениваются не очень существенными объемами данных, но очень интенсивно. Используются коллективные операции на каждом шаге с небольшими порциями данных, что объясняет такую картину. Также наблюдается меньший дизбаланс между процессами, чем наблюдаемый в графиках использования памяти, вычислений и передачи данных в байтах/сек. Это указывает на то, что процессы обмениваются по алгоритму одинаковым числом пакетов, однако получают разные объемы данных и ведут неравномерные вычисления.
На графике числа процессов, ожидающих вхождения в стадию счета (Loadavg), видно, что на протяжении всей работы программы значение этого параметра постоянно и приблизительно равняется 8. Это свидетельствует о стабильной работе программы с загруженными вычислениями всеми узлами. Это указывает на очень рациональную и статичную загрузку аппаратных ресурсов процессами. И показывает достаточно хорошую эффективность выполняемой реализации. В целом, по данным системного мониторинга работы программы можно сделать вывод о том, что программа работала достаточно эффективно, и стабильно. Использование памяти очень интенсивное, а использование коммуникационной среды крайне интенсивное, при этом объемы передаваемых данных не являются высокими. Это указывает на требовательность к латентности коммуникационной среды алгоритмической части программы. Низкая эффективность связана, судя по всему, с достаточно высоким объемом пересылок на каждом процессе и с интенсивными обменами сообщениями.
