Алгоритм Дейкстры: как работает и где используется

Зачем нужен этот алгоритм

Алгоритм Дейкстры используют для решения «задачи о кратчайших путях с единственным источником». Она заключается в поиске кратчайших путей от заданной вершины до всех остальных во взвешенном графе с неотрицательными весами.

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

• n — количество вершин в графе;
• m — количество ребер в графе;
• s — стартовая вершина.

Алгоритм Дейкстры выполняется за n итераций. На каждой итерации выбирается вершина v с минимальным значением d[v] среди непомеченных вершин. Эта вершина v затем отмечается как помеченная.

Далее на текущей итерации происходит этап релаксации. В этом этапе просматриваются все ребра (v, to), исходящие из вершины v, и проверяется, можно ли улучшить значение d[to].

То есть, если длина рассматриваемого ребра равна l, тогда d[to] = min(d[to], d[v] + l). При успешной релаксации, то есть когда удалось улучшить расстояние до вершины to, в массиве p указывается, что предшественником на кратчайшем пути к вершине to является вершина v, то есть p[to] = v.

На этом итерация заканчивается. 

По завершении n итераций все вершины графа оказываются помеченными, и алгоритм заканчивает выполнение.

Важно заметить, что если из начальной вершины s невозможно построить путь до некоторых вершин графа, их значения d[v] останутся бесконечными. Алгоритм можно завершить досрочно, как только будет выбрана вершина с бесконечным значением расстояния.

Рассмотрим работу алгоритма на примере. Будем искать кратчайшие пути от вершины 4. 

Изначально массивы u (посещений), d (расстояния) и p (предков) для графа из примера имеют следующие значения:

Изначальные значения

На первой итерации мы выбираем вершину v с наименьшим значением d[v]. Очевидно, что на первом шаге будет выбрана стартовая вершина — 4. 

Помечаем её посещённой u[4] = true.

Дальше проходим по всем соседям вершины 4 и пытаемся улучшить для них значения в массиве d. Для всех вершин, расстояние до которых удалось улучшить, в список предков записываем вершину 4. На первой итерации удалось улучшить расстояния до вершин 1, 5, 6. В результате значения массивов u, d, p изменились следующим образом: 

После первой итерации

На следующем шаге выбираем вершину 6. Улучшаем расстояния до вершин 3 и 7.

После второй итерации

Следующая непосещённая вершина с минимальным весом — 1. 

Расстояние от вершины 4 до вершины 1 равняется 3. Пытаемся улучшить расстояние до всех её соседей. Так, например, можно улучшить расстояние до вершины 5. Ранее оно было равно 8, а после релаксации это значение уменьшается: 

d[5] = min(d[5], d[1] + l) = min(8, 3 + 2) = 5.

После третьей итерации

И аналогичным образом мы проходим все оставшиеся итерации.

Выбираем непосещённую вершину с минимальным значением d[v]. На этой итерации будет выбрана вершина 7. Ни для одного её соседа длину кратчайшего пути улучшить не удалось. 

После четвёртой итерации

На следующей итерации будет посещена вершина 2. От неё удалось улучшить путь до вершин 0 и 3.

После пятой итерации

Далее посетив вершину 5 улучшаем путь до вершины 8.

После шестой итерации

На последующих итерациях помечаются посещёнными вершины 8, 0 и 3. От них нельзя улучшить путь ни до одного из их соседей.

После седьмой итерации

После восьмой итерации

После девятой итерации

После окончания работы алгоритма значения массивов u, d, p:

После десятой итерации

Реализация на C++

			vector <vector <pair <long long, long long> >> vP(n); // список смежности

vector <long long> d(n, INT_MAX); // кратчайшие пути
vector <long long> p(n, -1); // предки
vector <bool> used(n); // посещенные вершины

d[s] = 0; // обнуляем кратчайший путь для стартовой вершины
    
for (long long i = 0; i < n; i++) {
    long long v = -1;
    // Находим не посещенную вершину с минимальным d[j]
    for (long long j = 0; j < n; j++) {
        if (!used[j] && (v == -1 || d[j] < d[v])) {
            v = j;
        }
    }
    
    // Если расстояние до выбранной вершины равняется ∞, то выходим из алгоритма.
    if (d[v] == INT_MAX) {
        break;
    }
    // Отмечаем вершину v посещенной
    used[v] = true;
    
    // Проводим релаксацию. 
    for (long long j = 0; j < vP[v].size(); j++) { // Проходим по всем соседям выбранной вершины
        long long to = vP[v][j].first, l = vP[v][j].second;
        if (d[to] > d[v] + l) { // Проверяем, можно ли улучшить расстояния до соседа
            d[to] = d[v] + l; 
            p[to] = v;
        }
    }
}

		

Оценим скорость работы алгоритма. Он состоит из n итераций, внутри каждой из которых осуществляется поиск вершины с наименьшим значением d[v] (при простейшей реализации n итераций). Также за время работы алгоритма m раз производится попытка релаксации. 

Таким образом асимптотика алгоритма равняется O(n^2+m).

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

Где используется

Этот алгоритм универсален, поэтому его можно использовать в разных сферах.

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

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

В системах бронирования для поиска наиболее быстрых и дешевых билетов с учетом возможных пересадок. 

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

Ограничения

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

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

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

Какие еще есть алгоритмы для поиска кратчайшего пути

Алгоритм Беллмана-Форда вычисляет кратчайшие пути от одной вершины ко всем остальным, но в отличие от алгоритма Дейкстры, способен работать с графами, имеющими рёбра с отрицательными весами. Его временная сложность составляет O(nm). Для графов с большим числом рёбер этот алгоритм может работать медленнее, чем Дейкстра.

Алгоритм Джонсона позволяет найти кратчайшие пути между всеми парами вершин. Он комбинирует алгоритмы Дейкстры и Беллмана-Форда и имеет временную сложность O(n^2 log n + nm). Он может быть более эффективным для графов с малым количеством ребер.

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

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

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

Алгоритм Флойда-Уоршелла предназначен для нахождения кратчайших путей между всеми парами вершин. Его временная сложность составляет O(n^3), что делает его менее эффективным для очень больших графов, но он может быть выгодным для плотных графов с небольшим числом вершин.

Практика

Для закрепления темы вы можете порешать задачи на алгоритм Дейкстры на acmp.ru:

• 132. Алгоритм Дейкстры
• 1381. Алгоритм Дейкстры-2
• 1383. Дейкстра за O(M log N)
  
• 133. Заправки
• 134. Автобусы
• 1382. Транспортировка
• 469. Химическая тревога
• 1384. Защищенное соединение