Написать пост

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

Как выбрать оптимальный маршрут для автомобиля или определить самый выгодный вариант перелёта с учетом возможных пересадок? Алгоритм Дейкстры предлагает эффективное решение задачи поиска в графе кратчайших путей от заданной вершины. Разбираем подробнее.

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

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

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

  • 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 (предков) для графа из примера имеют следующие значения:

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм Дейкстры: как работает и где используется 5
После четвёртой итерации

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

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

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

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

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

Алгоритм Дейкстры: как работает и где используется 8
После седьмой итерации
Алгоритм Дейкстры: как работает и где используется 9
После восьмой итерации
Алгоритм Дейкстры: как работает и где используется 10
После девятой итерации

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

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

Реализация на 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:

Следите за новыми постами
Следите за новыми постами по любимым темам
1К открытий11К показов