7 января 2011 в 00:34

Алгоритм Дейкстры. Поиск оптимальных маршрутов на графе из песочницы

Из многих алгоритмов поиска кратчайших маршрутов на графе, на Хабре я нашел только описание алгоритма Флойда-Уоршалла. Этот алгоритм находит кратчайшие пути между всеми вершинами графа и их длину. В этой статье я опишу принцип работы алгоритма Дейкстры, который находит оптимальные маршруты и их длину между одной конкретной вершиной (источником) и всеми остальными вершинами графа. Недостаток данного алгоритма в том, что он будет некорректно работать если граф имеет дуги отрицательного веса.

Для примера возьмем такой ориентированный граф G:

image



Этот граф мы можем представить в виде матрицы С:

image

Возьмем в качестве источника вершину 1. Это значит что мы будем искать кратчайшие маршруты из вершины 1 в вершины 2, 3, 4 и 5.
Данный алгоритм пошагово перебирает все вершины графа и назначает им метки, которые являются известным минимальным расстоянием от вершины источника до конкретной вершины. Рассмотрим этот алгоритм на примере.

Присвоим 1-й вершине метку равную 0, потому как эта вершина — источник. Остальным вершинам присвоим метки равные бесконечности.

image

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

image

После того как мы рассмотрели все вершины, в которые есть прямой путь из W, вершину W мы отмечаем как посещённую, и выбираем из ещё не посещенных такую, которая имеет минимальное значение метки, она и будет следующей вершиной W. В данном случае это вершина 2 или 5. Если есть несколько вершин с одинаковыми метками, то не имеет значения какую из них мы выберем как W.

Мы выберем вершину 2. Но из нее нет ни одного исходящего пути, поэтому мы сразу отмечаем эту вершину как посещенную и переходим к следующей вершине с минимальной меткой. На этот раз только вершина 5 имеет минимальную метку. Рассмотрим все вершины в которые есть прямые пути из 5, но которые ещё не помечены как посещенные. Снова находим сумму метки вершины W и веса ребра из W в текущую вершину, и если эта сумма будет меньше предыдущей метки, то заменяем значение метки на полученную сумму.

image

Исходя из картинки мы можем увидеть, что метки 3-ей и 4-ой вершин стали меньше, тоесть был найден более короткий маршрут в эти вершины из вершины источника. Далее отмечаем 5-ю вершину как посещенную и выбираем следующую вершину, которая имеет минимальную метку. Повторяем все перечисленные выше действия до тех пор, пока есть непосещенные вершины.

Выполнив все действия получим такой результат:

image

Также есть вектор Р, исходя из которого можно построить кратчайшие маршруты. По количеству элементов этот вектор равен количеству вершин в графе, Каждый элемент содержит последнюю промежуточную вершину на кратчайшем пути между вершиной-источником и конечной вершиной. В начале алгоритма все элементы вектора Р равны вершине источнику (в нашем случае Р = {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}.

Зная что в каждом элементе вектора Р записана последняя промежуточная вершина на пути между источником и конечной вершиной, мы можем получить и сам кратчайший маршрут.

По данной ссылке находится программа, написанная на С++, которая показывает на примере работу алгоритма Дейкстры (исходники прилагаются).
+33
56381
188
splitface 12,5

Комментарии (31)

+7
tkirill128, #
Всегда интересно почитать очередной ликбез по какому-нибудь популярному алгоритму :)
0
rusy, #
вот здесь неплохие иллюстрации к алгоритму Дейкстры
+3
BlastBeat, #
Classic. Имхо, с этого алго начинается понимание графов.
+2
XaosSintez, #
есть алгоритмы на графы и чуть попроще. Поиск в глубину\ширину например. Лично я с них начинал :)
–1
BlastBeat, #
Согласен, но поиски базовые и очевидные, а с этого начинаются изящества графов)
0
DankoUA, #
Алгоритм Флойда-Варшалла хоть и программируется в одну строчку, но его корректность не так уж и очевидна.
–1
Laytlas, #
А, что же вы делаете! Нельзя забывать о табуляции, иначе получается быдло-код.
Алгоритм флойда записывается в 3 строчки! (во всяком случае его основная суть)
0
burdakovd, #
тогда уже в четыре: три оператора цикла + строчка собственно кода
Это если не считать строчки с операторными скобками
+11
mihaildemidoff, #
не думаю что Дейкстра настолько сложный и необычный в реализации, чтобы использовать его в качестве статьи на хабре. Да и начинать надо было с dfs, bfs.
Еще есть такой вопрос, почему вы используете матрицу смежности, а не списки?
Вот из кода:
int MAX=0; //вместо бесконечности
почему ноль, когда у нас может быть ребро с весом ноль? бесконечность != 0. Нужен пример графа, когда алгоритм неверно сработает?
в проекте «Unit1.cpp» строки [50-61], не лень было ручками-то писать?
–6
splitface, #
Написанию программы я уделил не так много времени, потому и код не идеален. А переменная int MAX в функции setMAX() меняется на сумму всех элементов матрицы умноженную на два.
+4
mihaildemidoff, #
имеем следующий орграф(список смежности)в виде (смежная вершина, вес ребра):
вершина 1) (2,0) (3,6)
вершина 2) (4,5)
вершина 3) (4,7)
вершина 4) (5,8)
Ваша программа говорит нам о следующем:
Кратчайшие маршруты:
1 -> 3 = 6
1 -> 3 -> 4 = 13
1 -> 3 -> 4 -> 5 = 21
и это всё.
а ваша функция делает лишний N*N, притом эта функция выполняется единожды по нажатию кнопки.(возможно не прав, код тяжелочитаемый).
А код должен быть не идеальным, а хотя бы правильным и читаемым, тем более вы предоставили его на публике.
0
Intilt, #
Согласен, даже в русской Википедии данный алгоритм описан достаточно подробно и очень понятно.
–4
Monca, #
Спасибо, действительно все просто и понятно. Не умаляет статью и то, что сам алгоритм простой довольно.
Кстати, Дейкстра — это первый программист! Именно он написал это слово в качестве своей профессии в документах (точно не помню, кажется в свидетельстве о браке).
+1
Hexenlord, #
> Этот граф мы можем представить в виде матрицы С:

И дальше повторяется исходный рисунок. Кажется, Вы что-то забыли :)
–1
splitface, #
Спасибо. Исправил.
+9
Wildy, #
дожились
0
smartly, #
На графике вес из 1 в 5 обозначен как 10, а в талице — 80. В обратном направлении — в таблице вообще не указан вес.
+2
Latobco, #
Можно было припомнить Флойда-Уоршалла и Форда-Беллмана, так как Дейкстра работает только для дуг из неотрицательными весами, а Флойд-Уоршалл — для всег весов и Форд-Беллман для релаксации…
0
iambot, #
Если я не ошибаюсь, то ошиблись вы:
Р = {1, 1, 5, 1, 5} -> {1,1,5,5,1}
Да вы, кажется, и сами об этом пишите:
«4-му элементу вектора Р значение W — P[4]=5»
–1
iPavel, #
1. А как, используя вектор P получить путь к вершине, если он проходит через 5 точек, а не через одну? Если я понял верно, то делать то же самое заново, но для этой предпоследней точки? както долго выглядит…
2. А почему «он будет некорректно работать если граф имеет дуги отрицательного веса.»?
+1
XaosSintez, #
Это следует из аксиомы, на которую опирается данный алгоритм. Что при неотрицательных весах ребер кратчайший путь от одной вершины в другую смежную — прямой (с минимальной стоимостью за один шаг). Формулировка неточная, точную так сходу не вспомню. Но суть передал
0
vladsharikov, #
Тот же вопрос имеется. Сейчас нужно написать такую же программу как в заголовке можно сказать. Пока решаю на бумажке, думаю над этим вектором P.

Вот матрица:
0 3 0 0 7 0 0 0 0
3 0 4 9 0 0 0 0 0
0 4 0 0 0 2 8 0 0
0 9 0 0 0 7 0 0 4
7 0 0 0 0 0 1 0 0
0 0 2 7 0 0 1 7 0
0 0 8 0 1 1 0 2 0
0 0 0 0 0 7 2 0 0
0 0 0 4 0 0 0 0 0

Или граф:


Наикратчайший маршрут из 7 из 9 такой: 7->6->4->9. Делая как предлагает автор, я получил вектор P = {1,1,6,1,1,1,1,1,4}. Из этого следует, что в 3 вершину путь такой: 7 -> 6 -> 3 — правильно. Но в 9 такой: 7 -> 4 -> 9. Это неправильно. Я что-то не так сделал? Вроде все как сказано здесь.
+1
sige, #
А мне нравятся такие неправильного вида крестики, нарисованные мышкой, которые показывают с какой любовью мы расстаемся с просмотренной вершиной :)
0
und, #
Ох как раз сегодня экзамен писал по Теории Телетрафика…
0
ntkt, #
Спасибо Вам, испытал сладостное чувство ностальгии по своей исследовательскую работе в 10 классе.
Тогда я реализовывал и сравнивал различные алгоритмы поиска пути на графах, в итоге остановился на А* и подбирал для него хорошую эвристику на двумерной карте с движущимися препятствиями. К счастью, я потерял ее исходники в тот же год, и теперь я не умру от стыда, читая свой код.
+1
susl, #
А еще, для полноты картины, было бы неплохо рассказать почему алгоритм работает (и почему не работает при отрицательных весах).
+4
goodman, #
Не то чтобы я хотел обидеть автора, но не вижу смысл в таких постах. Это либо проходит в университете на предмете «Алгоритмы и структуры данных» или в том же гугле и даже на хабре уже это всё расписано.
+2
dslf, #
<зануда>
Ну и зачем в очередной раз разжевывать этот почти всем известный алгоритм?
Во всяком случае, это лучше чем писать посты о нвых айфонах.
</зануда>
НЛО прилетело и опубликовало эту надпись здесь
НЛО прилетело и опубликовало эту надпись здесь
0
goodman, #
Не то что анализа, вы нашли в тексте данной статьи, сложность этого алгоритма и чем он лучше других ему подобных?)

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.