Tag Archives: алгоритм Дейкстры. Нахождение кратчайших путей
По завершению турнира «Новогодняя ночь» спонсор решил отправить $m$ призерам подарки по почте. Зная количество участников $n$ и время доставки почты между некоторыми отделениями «Укрпочты», найти, через какое минимальное время последний из призеров получит свой приз.
Входные данные
Первая строка содержит $3$ числа: количество участников турнира $n$, количество призов спонсора $m$ и количество известных временных сроков доставки между некоторыми из отделений $k$. В следующей строке через пробел указаны номера участников, ставших призёрами.
Далее идет $k$ строк по $3$ числа в каждой с информацией об известных сроках доставки между некоторыми из отделений в формате: $a$ $b$ $t$, где $a$ и $b$ — номера отделений, $t$ $(0 \leqslant t \leqslant 365)$ — время доставки почты между ними. В последней строке находится единственное число — номер почтового отделения, из которого спонсор будет отправлять призы. Известно, что $1 \leqslant n, m, a, b \leqslant 365$.
Выходные данные
Если все призы будут доставлены участникам — вывести в первой строке «The good sponsor!», а в следующей — время, через какое последний из призеров получит свой приз. Если хотя бы один из участников не сможет получить приз — вывести в единственной строке «It is not fault of sponsor…». Фразы выводить без кавычек.
Тесты
| № | Входные данные | Выходные данные |
| 1. | 3 2 2 2 3 1 2 3 2 3 4 1 |
The good sponsor! 7 |
| 2. | 5 1 4 5 1 3 2 2 3 3 4 2 5 4 5 6 1 |
The good sponsor! 16 |
| 3. | 7 2 6 1 3 1 3 2 2 4 32 4 5 94 3 1 0 6 2 4 7 2 3 7 |
It is not fault of sponsor… |
| 4. | 5 2 6 1 2 3 1 1 3 4 2 2 4 3 5 1 4 4 5 5 2 3 7 2 |
The good sponsor! 6 |
Решить задачу о нахождении кратчайшего пути алгоритмом Дейкстры.
Найти кратчайший путь от Х0 до Х7. Граф задан элементами стоимостной матрицы
Построим этот граф
Начнем с элемента Х0 и присвоим ему метку 0, рассмотрим всех его соседей, т.к. там еще нет пометок, то присвоим им соответствующие длины:
Все соседи Х0 рассмотрены, помечаем ее и переходим к вершине Х1. ЕЕ соседи Х0, Х2,Х4, но Х0 помечена, не рассматриваем ее. Для Х2: 
, оставляем метку.
Для Х4: 
, заменяем метку. Все соседи вершины Х1 рассмотрены, помечаем ее
переходим к вершине Х2. ЕЕ соседи Х0, Х1,Х3, Х4, Х5, Х6, но Х0, Х1 помечены, не рассматриваем их.
Для Х3: 
, оставляем метку.
Для Х5: 
, заменяем метку.
Для Х4: 
, оставляем метку.
Для Х6: 
, заменяем метку.
Все соседи вершины Х2 рассмотрены, помечаем ее.
переходим к вершине Х3. ЕЕ соседи Х0, Х2, Х6, но Х0, Х2 помечены, не рассматриваем их.
Для Х6: 
, оставляем метку.
Все соседи вершины Х3 рассмотрены, помечаем ее.
переходим к вершине Х4. ЕЕ соседи Х1,Х2, Х5, Х7, но Х1, Х2 помечены, не рассматриваем их.
Для Х5: 
, заменяем метку.
Для Х7: 
, заменяем метку.
Все соседи вершины Х4 рассмотрены, помечаем ее.
переходим к вершине Х5. ЕЕ соседи Х2,Х4, Х6, Х7, но Х2, Х4 помечены, не рассматриваем их.
Для Х6: 
, оставляем метку.
Для Х7: 
, оставляем метку.
Все соседи вершины Х5 рассмотрены, помечаем ее.
переходим к вершине Х6. ЕЕ соседи Х2,Х3, Х5, Х7, но Х2, Х3, Х5 помечены, не рассматриваем их.
Для Х7: 
, оставляем метку.
Все соседи вершины Х6 рассмотрены, помечаем ее. И помечаем оставшуюся Х7, все вершины рассмотрены.
Вывод: Кратчайший путь их Х0 в Х7 имеет длину 101, этот путь: Х7-Х4-Х1-Х0.
Кратчайший путь рассматривается при помощи некоторого математического объекта, называемого графом. Поиск кратчайшего пути ведется между двумя заданными вершинами в графе. Результатом является путь , то есть последовательность вершин и ребер, инцидентных двум соседним вершинам, и его длина .
Рассмотрим три наиболее эффективных алгоритма нахождения кратчайшего пути :
- алгоритм Дейкстры ;
- алгоритм Флойда ;
- переборные алгоритмы.
Указанные алгоритмы легко выполняются при малом количестве вершин в графе. При увеличении их количества задача поиска кратчайшего пути усложняется.
Алгоритм Дейкстры
Данный алгоритм является алгоритмом на графах, который изобретен нидерландским ученым Э. Дейкстрой в 1959 году. Алгоритм находит кратчайшее расстояние от одной из вершин графа до всех остальных и работает только для графов без ребер отрицательного веса.
Каждой вершине приписывается вес – это вес пути от начальной вершины до данной. Также каждая вершина может быть выделена. Если вершина выделена, то путь от нее до начальной вершины кратчайший, если нет – то временный. Обходя граф , алгоритм считает для каждой вершины маршрут , и, если он оказывается кратчайшим, выделяет вершину. Весом данной вершины становится вес пути. Для всех соседей данной вершины алгоритм также рассчитывает вес , при этом ни при каких условиях не выделяя их. Алгоритм заканчивает свою работу, дойдя до конечной вершины, и весом кратчайшего пути становится вес конечной вершины.
Алгоритм Дейкстры
Шаг 1. Всем вершинам, за исключением первой, присваивается вес равный бесконечности, а первой вершине – 0.
Шаг 2. Все вершины не выделены.
Шаг 3. Первая вершина объявляется текущей.
Шаг 4. Вес всех невыделенных вершин пересчитывается по формуле: вес невыделенной вершины есть минимальное число из старого веса данной вершины, суммы веса текущей вершины и веса ребра , соединяющего текущую вершину с невыделенной.
Шаг 5. Среди невыделенных вершин ищется вершина с минимальным весом. Если таковая не найдена, то есть вес всех вершин равен бесконечности, то маршрут не существует. Следовательно, выход . Иначе, текущей становится найденная вершина . Она же выделяется.
Шаг 6. Если текущей вершиной оказывается конечная, то путь найден, и его вес есть вес конечной вершины.
Шаг 7. Переход на шаг 4.
В программной реализации алгоритма Дейкстры построим множество S вершин, для которых кратчайшие пути от начальной вершины уже известны. На каждом шаге к множеству S добавляется та из оставшихся вершин, расстояние до которой от начальной вершины меньше, чем для других оставшихся вершин. При этом будем использовать массив D , в который записываются длины кратчайших путей для каждой вершины. Когда множество S будет содержать все вершины графа , тогда массив D будет содержать длины кратчайших путей от начальной вершины к каждой вершине.
Помимо указанных массивов будем использовать матрицу длин C , где элемент C – длина ребра (i,j) , если ребра нет, то ее длина полагается равной бесконечности, то есть больше любой фактической длины ребер. Фактически матрица C представляет собой матрицу смежности , в которой все нулевые элементы заменены на бесконечность.
Для определения самого
До каждого города области (если двигаться можно только по дорогам).
Вариант 2. Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Стоимость перелёта из A в B может быть не равна стоимости перелёта из B в A. Найти маршрут минимальной стоимости (возможно, с пересадками) от Копенгагена до Барнаула .
Формальное определение
Пример
Рассмотрим выполнение алгоритма на примере графа, показанного на рисунке.
Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.
Реализации на языках программирования
Исполнение в языке С(Си)
#define SIZE 6 #define INF 1000000000 int a [ SIZE ][ SIZE ] = {{ INF , 5 , INF , INF , INF , INF },{ 1 , 2 , 3 , 4 , 5 , 6 }, // матрица путей { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }, // индексы по горизонтали из точки { 1 , 2 , 3 , 4 , 5 , 6 },{ 1 , 2 , 3 , 4 , 5 , 6 }}; // по вертикали в точку, значение - вес int d [ SIZE ]; // массив найденных кратчайших путей, индексы - вершины графа void deikstra () { int v [ SIZE ]; // массив меток int temp , i ; int minindex , min ; for (i = 0 ; i < SIZE ; i ++ ) { d [ i ] = INF ; // массив путей инициализируется бесконечностью v [ i ] = 1 ; } d [ 0 ] = 0 ; do { // исполнение алгоритма minindex = INF ; min = INF ; for (i = 0 ; i < SIZE ; i ++ ) { if ((v [ i ] == 1 ) && (d [ i ] < min )) { min = d [ i ]; minindex = i ; } } if (minindex != INF ) { for (i = 0 ; i < SIZE ; i ++ ) { if (a [ minindex ][ i ] > 0 ) { temp = min + a [ minindex ][ i ]; if (temp < d [ i ]) d [ i ] = temp ; } } v [ minindex ] = 0 ; } } while (minindex < INF ); }
Алгоритм Дейкстры – алгоритм на графах, который находит кратчайший путь между двумя данными вершинами в графе с неотрицательными длинами дуг. Также часто ставится задача расчёта кратчайшего пути от данной вершины до всех остальных. Алгоритм широко применяется в программировании, например, его используют протоколы маршрутизации.
Описание
На вход алгоритма подаётся взвешенный ориентированный граф с дугами неотрицательного веса. На выходе получается набор кратчайших путей от данной вершины до других.
В начале расстояние для начальной вершины полагается равным нулю, а расстояния до всех остальных понимаются бесконечными. Массив флагов, обозначающих то, пройдена ли вершина, заполняется нулями. Затем на каждом шаге цикла ищется вершина с минимальным расстоянием до изначальной и флагом равным нулю. Для неё устанавливается флаг и проверяются все соседние вершины. Если рассчитанное ранее расстояние от исходной вершины до проверяемой больше, чем сумма расстояния до текущей вершины и длины ребра от неё до проверяемой вершины, то расстояние до проверяемой вершины приравниваем к расстоянию до текущей+ребро от текущей до проверяемой. Цикл завершается, когда флаги всех вершин становятся равны 1, либо когда расстояние до всех вершин c флагом 0 бесконечно. Последний случай возможен тогда и только тогда, когда граф несвязеный.
Алгоритм Дейкстры в псевдокоде
Вход: С : array of real – матрица длин дуг графа; s – вершина, от которой ищется кратчайший путь и t – вершина, к которой он ищется.
Выход: векторы Т: array of real; и Н: array of 0..р. Если вершина v лежит на кратчайшем пути от s к t, то T[v] - длина кратчайшего пути от s к у; Н[у] - вершина, непосредственно предшествующая у на кратчайшем пути.
Н – массив, в котором вершине n соответствует вершина m, предыдущая на пути к n от s.
T – массив, в котором вершине n соответствует расстояние от неё до s.
X – массив, в котором вершине n соответствует 1, если путь до неё известен, и 0, если нет.
инициализация массивов:
for v from 1 to р do
Т[ v ]: = ∞ { кратчайший путь неизвестен }
X[v]: = 0 { все вершины не отмечены}
H[s]: = 0 { s ничего не предшествует }
T[s] : = 0 { кратчайший путь имеет длину 0...}
X[s] : = 1 { ...и он известен } v : = s { текущая вершина }
М: { обновление пометок }
for и ∈ Г(и ) do
if Х[и] = 0 & Т[и] > T[v] + C then
Т[и] : = T[v] + C { найден более короткий путь из s в и через v }
H[u]: = v { запоминаем его }
m : = ∞
v : = 0
{ поиск конца кратчайшего пути }
for и from 1 to p do
if X[u] = 0 &T[u] < t then
v: = u ;
m: = T[u] { вершина v заканчивает кратчайший путь из s
if v = 0 then
stop { нет пути из s в t } end if
if v = t then
stop { найден кратчайший путь из s в t } end if
X[v]: = 1 { найден кратчайший путь из s в v } goto M
Обоснование
Для доказательства корректности алгоритма Дейкстры достаточно заметить, что при каждом выполнении тела цикла, начинающегося меткой М, в качестве v используется вершина, для которой известен кратчайший путь из вершины s. Другими словами, если X[v] = 1, то T[v] = d(s,v), и все вершины на пути (s,v), определяемом вектором Н, обладают тем же свойством, то есть
Vu Т[и] = 1 => Т[и] = d(s,u)&T] = 1.
Действительно (по индукции), первый раз в качестве v используется вершина s, для которой кратчайший путь пустой и имеет длину 0 (непустые пути не могут быть короче, потому что длины дуг неотрицательны). Пусть Т[u] = d(s,u) для всех ранее помеченных вершин и. Рассмотрим вновь помеченную вершину v , которая выбрана из условия T[v] = min Т[и]. Заметим, что если известен путь, проходящий через помеченные вершины, то тем самым известен кратчайший путь. Допустим (от противного), что T[v]> d(s, v), то есть найденный путь, ведущий из s в v, не является кратчайшим. Тогда на этом пути должны быть непомеченные вершины. Рассмотрим первую вершину w на этом пути, такую что T[w]= 0.Имеем: T[w]= d(s,w)⩽d(s>v) < Т[v],что противоречит выбору вершины u.
Временная сложность
Сложность алгоритма Дейкстры зависит от способа нахождения не посещённой вершины с минимальным расстоянием до изначальной, способа хранения множества непосещённых вершин и способа обновления меток. Пусть n количество вершин, а через m - количество рёбер в графе. Тогда в простейшем случае, когда для поиска вершины с минимальным расстоянием до изначальной вершины просматривается всё множество вершин, а для хранения расстояний используется массив, время работы алгоритма - О(n 2). Основной цикл выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций. На циклы по соседям каждой посещаемой вершины тратится количество операций, пропорциональное количеству рёбер m (поскольку каждое ребро встречается в этих циклах ровно дважды и требует константное число операций). Таким образом, общее время работы алгоритма O(n 2 +m), но, так как m много меньше n(n-1), в конечном счёте получается О(n 2).
Для разреженных графов (то есть таких, для которых m много меньше n²) непосещённые вершины можно хранить в двоичной куче, а в качестве ключа использовать значения расстояний. Так как цикл выполняется порядка n раз, а количество релаксаций (смен меток) не больше m, время работы такой реализации - О(nlogn+mlogn)
Пример
Вычисление расстояний от вершины 1 по проходимым вершинам: