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

690
1 Звезда2 Звезды3 Звезды4 Звезды5 Звезд (1 оценок, среднее: 5,00 из 5)
Загрузка...
  • Название: Dijkstra;
  • Применение: Поиск кратчайшего пути в графах;
  • Время выполнения: O(n²+ E);
  • Сложность: Средний;
  • Входные параметры: Заданный узел графа;  Взвешенный ациклический граф c положительными весами;
  • Результат: Кратчайшее расстояние от заданной вершины графа до всех остальных узлов

Пример из жизни:

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

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

Давайте представим себя на месте курьера пиццы. Допустим нам дали некоторое время на обдумывание задачи. Что делать? Для начала надо представить себе маршрут, поэтому следует подобрать соотвествующую абстракцию в виде структуры данных. Но как посторить маршрут по точкам или каким-то другим способом? Разумней представить маршрут таким какой он есть, а значит изобразить множество «отрезков», соедниняющих потенциальные маршруты следования.

Давайте обозначим пункты остановки или начала следования цифрами (в произвольном порядке). Соедними каждый пукт отрезком и подпишем его временем преодоления этого расстояния. Наверное очень напоминает граф. Действительно получилась математическая абстракция в виде графа с положительными весами (за веса примем время доставки). Более подробно про графы читайте тут. Теперь появилась полноценная карта следования, которая не только визуализировала нашу задачу, но и позвоила выдвинуть некоторые смелые идеи.

Теперь можно сделать гипотезу, основанную на здравом смысле! Если следовать кратчайшими путями от одной точки в другую, то и получится самый быстрый путь! Проверим нашу гипотезу на практике. Итак, чтобы добраться до клиента из точки 1 в точку 6 необходимо просчитать маршрут с наименьшим временем. Определим кратчайший маршрут на основе выбора минимального маршрута из возможных.

Если начинаем двигаться из точки 1 у нас встает выбор переместиться в 3 или 5. Следуя нашей логики выбираем минимальное время достижения цели — значит 3. В точке 3 встает аналогичный выбор маршрута — выбираем 10 и т.д. получается  следующий маршрут следования, обозначенный красной линией. Время затраченное на достижении цели = 32 мин.

Постойте! А если отправить из точки 1 в 4, а затем в 6, затраченое время вего 19 мин. Ну как так!? А если выйти из 1 в 3, а потом попасть из 3 в 6, получится опять 19 мин. И как быть? решать задачу перебором? Зебегая вперед, можно сказать, что данная задача решатся с помощью Алгоритма Дейкстры и никакого перебора здесь не нужно!

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

Постановка задачи:

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

Линвистическое описание:

Основная идея алгоритма состоит в создании двух областей. В первую облась будут попадать обработанные вершины графов, во вторую необработанные. Устанавливается заданная вершина (или вершина источник) расстояние до которой считается равно = 0, все остальные вершины считаются необработанными и расстояние до них считается бесконечным. На каждом шаге выбирается вершина из небоработанной области с минимальным расстоянием и обрабатывается. Обрабатывается следующим образом: прибавляется вес ребра к вычисленному минимальному значению узла. Если полученное значение меньше, чем исходное (уже известное), то происходит пересчет значения узла. Данная процедура повторяется пока не останется значений в необработанной области и все вершины графа будут обработаны. Конечно ничего не понятно! Предлагаю сварить горячее кофе и пропустить пару чашек, а после дочитать до конца:)

Реализация:

Допустим наша исходная вершина обозначена цифрой 1. Теперь выбираем исходящие из этой вершины ребра, как видно их всего три. Это ребра с весами 10, 8 и 6. Присваиваем кратчайшие пути вершине 5 (10), 4 (8) и 3 (6). Обратите внимание вершины с обозначением 2 и 6 имеют бесконоченые кратчайшие пути, потому что мы не можем добраться до них из вершины 1 напрямую и считается, что это расстояние бесконечно.

Родитель Узел Стоимость
1 5 10
1 4 8
1 3 6
2
6
рис.1 

Теперь выбираем кратчайшее расстояние от вершины 1. Это расстояние равно 6. Итак, первый узел под номером 1 считается обработанным поместим его в обработанную «кучу» и на время забудем про него —  теперь он не учавствует в алгоритме. Выбираем наименьшее расстояние, присвоенное узлам — обозначены оранжевым цветом. Минимальное расстояние  узла 3 равно 6.  Начинаем работать с ним. Смотрим исходящие дуги  из узла 3 — такая одна, и ведет она в вершину 6. Так как у нас уже было минимальное расстояние в вершине 3 мы прибавляем его к весу ребра ведущего из вершины 3 в 6 — получается 6+13 = 19.

Родитель Узел Стоимость
1 5 10
1 4 8
1 3 6
2
3 6 19
рис.2

Наступает важный момент! Необходимо произвести сравнение бесконечного расстояния, которое было у вершины 6 с новым значением т.е. 19. Безусловно 19 гораздо меньше, чем «целая» бесконечность, поэтому необходимо обновить вес минимального расстояния до данного узла т.е. 19. Таким образом  узел 3 считается обработанным и можно приступать к поиску следующего «минимального» узла.

Родитель Узел Стоимость
1 5 10
1 4 8
1 3 6
2
3 6 19
рис.3

Таким узлом можно считать вершину графа под номером 4 с минимальным, присвоенным  расстоянием = 8 ( т.к. 8 < 10 и < 19). Теперь производим аналогичную операцию. Определяем исходящие ребра, а таких три с весами 2, 11 и 10. Но так как вершина 3 уже вышла из «игры» и считается обработанной у нас остаются только две вершины под номерами 5 (с весом = 2) и 6 (с весом = 11). Прибавляем 8 + 2 получется 10, т.к. 10 равно десяти (старому значению) обновление минимального расстояния до вершины 5 производить не будем. Аналогично считаем новое значение минимального расстояния до вершины графа 6.

Родитель Узел Стоимость
1 5 10
1 4 8
1 3 6
5 2 18
3 6 19
рис.4

Помещаем вершину 4 в обработанную область и выбираем значение наименьшего расстояния среди доступных или необработанных вершин (10, 18, 19). Подходит 10 и повторяем операцию снова.

Родитель Узел Стоимость
1 5 10
1 4 8
1 3 6
5 2 18
3 6 19
 рис.5

Помещаем 5 в обработанную область и повторяем операцию снова. Теперь наименьшее значение из необработанных вершин — 18. Существует только одно исходящее ребро с весом — 6. Пересчитываем значение минимально расстояния (18+6 = 24). Т.к. 24 больше 19 то не обновляем значения расстояни до вершины 6.

Родитель Узел Стоимость
1 5 10
1 4 8
1 3 6
5 2 18
3 6 19
 рис.6

К сожалению от вершины 6 мы не можем двигаться никуда т.к. не существует исходящих ребер, поэтому и считать нечего. Получется мы можем сразу поместить эту вершину в обработанную область. Следовательно, у нас больше не осталось необработанных вершин — значит алгоритм завершился.

Родитель Узел Стоимость
1 5 10
1 4 8
1 3 6
5 2 18
3 6 19
 рис.7

Посмотрите внимательно на эту картинку (рис 7 слева), что она нам может сказать? Как теперь определить кратчайшее расстояние, например, до вершины 2 ? Опять много вопросов и мало ответов — давайте разбираться. И вообще, что нам с этим делать?

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

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

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

Давайте разберем конкретный случай. На первом шаге рис.2, когда первый узел считается обработанным у нас были пересчитаны три узла 5, 4 и 3. У этих узлов появились значения минимальных расстояний 10, 8 и 6 соотвественно. Значит можно считать родителями этих узлов обработанный начальный узел — 1. Обратите внимание на рис.4. Как только мы пересчитали вес узла 2, то сразу обновили родителя для этого узла — родителем является обработанный узел — 5. Соотвественно, когда все узлы считаются обработанными, то получается таблица связей рис.7. По этой таблице можно построить любой маршрут. Например, самый короткий путь до 6 узла, будет выглядить как установление его родиля, а это узел 3 и соотвественно установление родителя у узла 3 — это узел под 1 номером, если у узла были родители то операция повторялась бы до тех пор пока не был найден начальный узел. В нашем случае повтроюсь это узел 1.

Программная разработка:

Давайте продумаем нашу программу. Во-первых, необходмо предусмотреть как минимум четыре массива: для весов ребер графа, для стоимости узла графа, для таблицы связей (родитель -> узел) и обработанную «кучу» узлов. Давайте начнем по порядку: инициализируем массив для весов ребер графа. Как правило, граф представляется в виде массива.

Давайте приведем полный код алгоритма Дейкстры,

В результате получаем ответ в массив зависимости родителя (откуда мы пришли) от узла (до куда мы ходим добраться)

и стоимости узлов вершин графа.

Время выполнения:

Осталось определить скорость времени выполнения данного алгоритма. В данном примере представления графов было реализовано на основе массива. Если вершины хранятся в простом массиве и для поиска минимума используется алгоритм линейного поиска, временная сложность алгоритма Дейкстры составляет O(n*n+ E) = O(n²). E — количество не помеченных вершин и E раз проводим релаксацию

Поделиться

Отправить ответ

avatar
wpDiscuz