Введение
Как способ найти кратчайший путь по числу рёбер в невзвешенном графе — для взвешенного графа (где у разных связей разная «стоимость») нужен другой алгоритм. В этой статье разберём алгоритм Дейкстры, классическое решение для поиска кратчайшего пути по суммарному весу в графе с неотрицательными весами рёбер, и его практическое применение, от навигационных систем до маршрутизации сетевых пакетов (тема, затронутая концептуально в сетевом цикле основного плана).
Концепция
Алгоритм Дейкстры поддерживает множество вершин с уже окончательно определённым минимальным расстоянием от старта, и на каждом шаге выбирает ещё не обработанную вершину с минимальным текущим известным расстоянием, «фиксирует» это расстояние как окончательное, и обновляет (релаксирует) расстояния её соседей, если путь через эту вершину короче ранее известного — повторение этого процесса до обработки всех достижимых вершин гарантированно даёт кратчайшие расстояния от старта до каждой из них, при условии, что все веса рёбер неотрицательны (для графов с отрицательными весами нужен другой алгоритм, как Беллмана-Форда). Эффективная реализация использует приоритетную очередь (std::priority_queue) для быстрого извлечения вершины с минимальным текущим расстоянием на каждом шаге, без необходимости полного перебора всех необработанных вершин для этого поиска.
Пример кода
// Алгоритм Дейкстры с приоритетной очередью — взвешенный граф (например, расстояния между городами)
#include <queue>
#include <unordered_map>
#include <limits>
using WeightedGraph = std::unordered_map<QString, std::vector<std::pair<QString, double>>>;
// каждая вершина -> список пар (соседняя вершина, вес ребра до неё)
std::unordered_map<QString, double> dijkstra(const WeightedGraph &graph, const QString &start)
{
std::unordered_map<QString, double> distances;
for (const auto &[node, _] : graph) {
distances[node] = std::numeric_limits<double>::infinity(); // изначально все расстояния "бесконечны"
}
distances[start] = 0;
using QueueItem = std::pair<double, QString>; // (расстояние, вершина)
std::priority_queue<QueueItem, std::vector<QueueItem>, std::greater<>> pq;
// std::greater<> — МИН-куча: на верхушке всегда вершина с НАИМЕНЬШИМ расстоянием
pq.push({0, start});
while (!pq.empty()) {
auto [currentDist, current] = pq.top();
pq.pop();
if (currentDist > distances[current]) continue; // устаревшая запись в очереди — пропускаем
for (const auto &[neighbor, weight] : graph.value(current)) {
double newDist = currentDist + weight;
if (newDist < distances[neighbor]) { // нашли более короткий путь — релаксация
distances[neighbor] = newDist;
pq.push({newDist, neighbor});
}
}
}
return distances;
}
// Использование результата для построения навигационного маршрута
WeightedGraph cityGraph = {
{"Москва", {{"Тверь", 180.0}, {"Владимир", 190.0}}},
{"Тверь", {{"Москва", 180.0}, {"Санкт-Петербург", 530.0}}},
{"Владимир", {{"Москва", 190.0}}},
{"Санкт-Петербург", {{"Тверь", 530.0}}}
};
auto distances = dijkstra(cityGraph, "Москва");
qDebug() << "Расстояние до Санкт-Петербурга:" << distances["Санкт-Петербург"];
Пояснения к коду
std::priority_queue с std::greater<> создаёт мин-кучу (статья 465) вместо стандартной для priority_queue макс-кучи — это даёт эффективное извлечение вершины с наименьшим текущим расстоянием на каждой итерации, что является ключевой операцией алгоритма. Проверка currentDist > distances[current] обрабатывает ситуацию, когда одна и та же вершина была добавлена в очередь несколько раз с разными расстояниями (что нормально для этой реализации) — при извлечении устаревшей, более не актуальной записи (когда уже известно лучшее расстояние, найденное позже) эта запись просто пропускается без повторной обработки. Пример с городами показывает практическое применение — кратчайший путь от Москвы до Санкт-Петербурга оказывается не прямым (которого вообще нет в этом графе), а через Тверь, что алгоритм определяет автоматически, перебирая все возможные пути через релаксацию расстояний соседей.
Подводные камни
- Применение алгоритма Дейкстры к графу с отрицательными весами рёбер — алгоритм фундаментально предполагает, что после «фиксации» окончательного расстояния до вершины это расстояние больше не может быть улучшено, что верно только при неотрицательных весах; при наличии отрицательных весов это предположение нарушается, и алгоритм может выдать некорректный результат без какой-либо явной ошибки или предупреждения — для графов с отрицательными весами нужен алгоритм Беллмана-Форда (более медленный, но корректно обрабатывающий отрицательные веса) или явная предварительная проверка отсутствия отрицательных весов.
- Реализация без приоритетной очереди (наивный перебор всех необработанных вершин для поиска минимума на каждом шаге) для большого графа — наивная версия имеет сложность O(n²), тогда как версия с приоритетной очередью (как в примере) достигает O((n + m) log n), где m — число рёбер, что для больших, разреженных графов (типичных для реальных карт дорог или сетевых топологий) даёт принципиально иную, значительно лучшую практическую производительность.
- Использование алгоритма Дейкстры для поиска кратчайшего пути в графе, где «расстояние» реально означает что-то немонотонное (например, время в пути, зависящее от загруженности дороги в момент проезда, а не фиксированный вес ребра) — алгоритм предполагает фиксированные, статичные веса рёбер, и для динамически изменяющихся условий (трафик, зависящий от времени проезда через конкретный участок) нужны более сложные модификации алгоритма или совершенно другой подход, учитывающий эту динамику.
- Игнорирование того, что алгоритм Дейкстры находит кратчайшие пути от ОДНОЙ стартовой вершины до всех остальных, а не между всеми парами вершин одновременно — для задачи, требующей кратчайших путей между многими разными парами вершин (а не от единственного фиксированного старта), многократный запуск алгоритма Дейкстры для каждой нужной начальной вершины может быть неэффективен по сравнению со специализированными алгоритмами для всех пар вершин одновременно (как алгоритм Флойда-Уоршелла), и выбор подходящего алгоритма должен учитывать реальную форму конкретной задачи.