Как найти минимальный путь для графа

Базовые алгоритмы нахождения кратчайших путей во взвешенных графах

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

Сформулируем определения и задачу.
Графом будем называть несколько точек (вершин), некоторые пары которых соединены отрезками (рёбрами). Граф связный, если от каждой вершины можно дойти до любой другой по этим отрезкам. Циклом назовём какой-то путь по рёбрам графа, начинающегося и заканчивающегося в одной и той же вершине. И ещё граф называется взвешенным, если каждому ребру соответствует какое-то число (вес). Не может быть двух рёбер, соединяющих одни и те же вершины.
Каждый из алгоритмов будет решать какую-то задачу о кратчайших путях на взвешенном связном. Кратчайший путь из одной вершины в другую — это такой путь по рёбрам, что сумма весов рёбер, по которым мы прошли будет минимальна.
Для ясности приведу пример такой задачи в реальной жизни. Пусть, в стране есть несколько городов и дорог, соединяющих эти города. При этом у каждой дороги есть длина. Вы хотите попасть из одного города в другой, проехав как можно меньший путь.

Считаем, что в графе n вершин и m рёбер.
Пойдём от простого к сложному.

Алгоритм Флойда-Уоршелла

Находит расстояние от каждой вершины до каждой за количество операций порядка n^3. Веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер (иначе мы можем ходить по нему сколько душе угодно и каждый раз уменьшать сумму, так не интересно).
В массиве d[0… n — 1][0… n — 1] на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в качестве «пересадочных» в пути мы будем использовать вершины с номером строго меньше i — 1 (вершины нумеруем с нуля). Пусть идёт i-ая итерация, и мы хотим обновить массив до i + 1-ой. Для этого для каждой пары вершин просто попытаемся взять в качестве пересадочной i — 1-ую вершину, и если это улучшает ответ, то так и оставим. Всего сделаем n + 1 итерацию, после её завершения в качестве «пересадочных» мы сможем использовать любую, и массив d будет являться ответом.
n итераций по n итераций по n итераций, итого порядка n^3 операций.
Псевдокод:

прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет
d = g
for i = 1 ... n + 1
     for j = 0 ... n - 1
          for k = 0 ... n - 1
              if d[j][k] > d[j][i - 1] + d[i - 1][k]
                  d[j][k] = d[j][i - 1] + d[i - 1][k]
вывести d

Алгоритм Форда-Беллмана

Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n * m. Аналогично предыдущему алгоритму, веса могут быть отрицательными, но у нас не может быть циклов с отрицательной суммой весов рёбер.
Заведём массив d[0… n — 1], в котором на i-ой итерации будем хранить ответ на исходную задачу с ограничением на то, что в путь должно входить строго меньше i рёбер. Если таких путей до вершины j нет, то d[j] = 2000000000 (это должна быть какая-то недостижимая константа, «бесконечность»). В самом начале d заполнен 2000000000. Чтобы обновлять на i-ой итерации массив, надо просто пройти по каждому ребру и попробовать улучшить расстояние до вершин, которые оно соединяет. Кратчайшие пути не содержат циклов, так как все циклы неотрицательны, и мы можем убрать цикл из путя, при этом длина пути не ухудшится (хочется также отметить, что именно так можно найти отрицательные циклы в графе: надо сделать ещё одну итерацию и посмотреть, не улучшилось ли расстояние до какой-нибудь вершины). Поэтому длина кратчайшего пути не больше n — 1, значит, после n-ой итерации d будет ответом на задачу.
n итераций по m итераций, итого порядка n * m операций.
Псевдокод:

прочитать e // e[0 ... m - 1] - массив, в котором хранятся рёбра и их веса (first, second - вершины, соединяемые ребром, value - вес ребра)
for i = 0 ... n - 1
    d[i] = 2000000000
d[0] = 0
for i = 1 ... n
    for j = 0 ... m - 1
        if d[e[j].second] > d[e[j].first] + e[j].value
            d[e[j].second] = d[e[j].first] + e[j].value
        if d[e[j].first] > d[e[j].second] + e[j].value
            d[e[j].first] = d[e[j].second] + e[j].value
вывести d

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

Находит расстояние от одной вершины (дадим ей номер 0) до всех остальных за количество операций порядка n^2. Все веса неотрицательны.
На каждой итерации какие-то вершины будут помечены, а какие-то нет. Заведём два массива: mark[0… n — 1] — True, если вершина помечена, False иначе, d[0… n — 1] — для каждой вершины будет храниться длина кратчайшего пути, проходящего только по помеченным вершинам в качестве «пересадочных». Также поддерживается инвариант того, что для помеченных вершин длина, указанная в d, и есть ответ. Сначала помечена только вершина 0, а g[i] равно x, если 0 и i соединяет ребро весом x, равно 2000000000, если их не соединяет ребро, и равно 0, если i = 0.
На каждой итерации мы находим вершину, с наименьшим значением в d среди непомеченных, пусть это вершина v. Тогда значение d[v] является ответом для v. Докажем. Пусть, кратчайший путь до v из 0 проходит не только по помеченным вершинам в качестве «пересадочных», и при этом он короче d[v]. Возьмём первую встретившуюся непомеченную вершину на этом пути, назовём её u. Длина пройденной части пути (от 0 до u) — d[u]. len >= d[u], где len — длина кратчайшего пути из 0 до v (т. к. отрицательных рёбер нет), но по нашему предположению len меньше d[v]. Значит, d[v] > len >= d[u]. Но тогда v не подходит под своё описание — у неё не наименьшее значение d[v] среди непомеченных. Противоречие.
Теперь смело помечаем вершину v и пересчитываем d. Так делаем, пока все вершины не станут помеченными, и d не станет ответом на задачу.
n итераций по n итераций (на поиск вершины v), итого порядка n^2 операций.
Псевдокод:

прочитать g // g[0 ... n - 1][0 ... n - 1] - массив, в котором хранятся веса рёбер, g[i][j] = 2000000000, если ребра между i и j нет
d = g
d[0] = 0
mark[0] = True
for i = 1 ... n - 1
    mark[i] = False
for i = 1 ... n - 1
    v = -1
    for i = 0 ... n - 1
        if (not mark[i]) and ((v == -1) or (d[v] > d[i]))
            v = i
    mark[v] = True
    for i = 0 ... n - 1
        if d[i] > d[v] + g[v][i]
            d[i] = d[v] + g[v][i]
вывести d

Алгоритм Дейкстры для разреженных графов

Делает то же самое, что и алгоритм Дейкстры, но за количество операций порядка m * log(n). Следует заметить, что m может быть порядка n^2, то есть эта вариация алгоритма Дейкстры не всегда быстрее классической, а только при маленьких m.
Что нам нужно в алгоритме Дейкстры? Нам нужно уметь находить по значению d минимальную вершину и уметь обновлять значение d в какой-то вершине. В классической реализации мы пользуемся простым массивом, находить минимальную по d вершину мы можем за порядка n операций, а обновлять — за 1 операцию. Воспользуемся двоичной кучей (во многих объектно-ориентированных языках она встроена). Куча поддерживает операции: добавить в кучу элемент (за порядка log(n) операций), найти минимальный элемент (за 1 операцию), удалить минимальный элемент (за порядка log(n) операций), где n — количество элементов в куче.
Создадим массив d[0… n — 1] (его значение то же самое, что и раньше) и кучу q. В куче будем хранить пары из номера вершины v и d[v] (сравниваться пары должны по d[v]). Также в куче могут быть фиктивные элементы. Так происходит, потому что значение d[v] обновляется, но мы не можем изменить его в куче. Поэтому в куче могут быть несколько элементов с одинаковым номером вершины, но с разным значением d (но всего вершин в куче будет не более m, я гарантирую это). Когда мы берём минимальное значение в куче, надо проверить, является ли этот элемент фиктивным. Для этого достаточно сравнить значение d в куче и реальное его значение. А ещё для записи графа вместо двоичного массива используем массив списков.
m раз добавляем элемент в кучу, получаем порядка m * log(n) операций.
Псевдокод:

прочитать g // g[0 ... n - 1] - массив списков, в i-ом списке хранятся пары: first - вершина, соединённая с i-ой вершиной ребром, second - вес этого ребра
d[0] = 0
for i = 0 ... n - 1
    d[i] = 2000000000
for i in g[0] // python style
    d[i.first] = i.second
    q.add(pair(i.second, i.first))
for i = 1 ... n - 1
    v = -1
    while (v = -1) or (d[v] != val)
        v = q.top.second
        val = q.top.first
    q.removeTop
    mark[v] = true
    for i in g[v]
        if d[i.first] > d[v] + i.second
            d[i.first] = d[v] + i.second
            q.add(pair(d[i.first], i.first))
вывести d

vector<int> bfs(int s) {
    // длина любого кратчайшего пути не превосходит n - 1,
    // поэтому n - достаточное значение для "бесконечности";
    // после работы алгоритма dist[v] = n, если v недостижима из s
    vector<int> dist(n, n);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    return dist;
}

// теперь bfs принимает 2 вершины, между которыми ищется пути
// bfs возвращает кратчайший путь из s в t, или же пустой vector, если пути нет
vector<int> bfs(int s, int t) {
    vector<int> dist(n, n);
    vector<int> p(n, -1);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                p[u] = v;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    
    // если пути не существует, возвращаем пустой vector
    if (dist[t] == n) {
        return {};
    }

    vector<int> path;
    while (t != -1) {
        path.push_back(t);
        t = p[t];
    }
    
    // путь был рассмотрен в обратном порядке, поэтому его нужно перевернуть
    reverse(path.begin(), path.end());
    return path;
}

// INF - infinity - бесконечность
const long long INF = (long long) 1e18 + 1;

vector<long long> dijkstra(int s) {
    vector<long long> dist(n, INF);
    dist[s] = 0;
    vector<bool> used(n);
    
    while (true) {
        // находим вершину, из которой будем релаксировать
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && (v == -1 || dist[i] < dist[v])) {
                v = i;
            }
        }
        
        // если не нашли подходящую вершину, прекращаем работу алгоритма
        if (v == -1) {
            break;
        }
        
        for (auto &e : adj[v]) {
            int u = e.first;
            int len = e.second;
            if (dist[u] > dist[v] + len) {
                dist[u] = dist[v] + len;
            }
        }
    }
    
    return dist;
}

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

поиск пути (англ. Pathfinding) — термин в информатике и искусственном интеллекте, который означает определение компьютерной программой наилучшего, оптимального маршрута между двумя точками.

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

Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для ее решения^[⇨].

У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.

Значимость данной задачи определяется ее различными практическими применениями^[⇨]. Например, в GPS-навигаторах осуществляется поиск кратчайшего пути между точкой отправления и точкой назначения. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Если сумма длин дорог между перекрестками минимальна, тогда найденный путь самый короткий.

В задаче о кратчайшем пути (shortest-paths problem) задается взвешенный ориентированный граф G = (V, Е) с весовой функцией w : Е —> R, отображающей ребра на их веса, значения которых выражаются действительными числами. Вес (weight) пути р = (Vo, Vi,…, Vk) равен суммарному весу входящих в него ребер.

Вес кратчайшего пути (shortest-path weight) из вершины и в вершину v определяется соотношением

Тогда по определению
кратчайший путь (shortest path) из вершины и в вершину v — это любой путь, вес которого удовлетворяет соотношению w (р) = delta(u, v).

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

Алгоритм позволяет решить многие другие задачи, в том числе те, что перечислены ниже.

Рис 1 Кратчайший путь (A, B, D, F) между вершинами A и F в неориентированном графе без весов.

Рис 2 Кратчайший путь (A, C, E, D, F) между вершинами A и F во взвешенном ориентированном графе.

Поиск пути в играх

Поиск пути в контексте компьютерных игр касается пути, на котором движущийся объект ищет путь вокруг препятствий. Наиболее часто задача поиска пути возникает в стратегиях реального времени, в которых игрок дает задание игровым юнитам (единицам) двигаться через игровой уровень, который содержит препятствия. Кроме стратегий, задача поиска пути, так или иначе, в той или иной мере встречается в большинстве современных игровых жанров. Так как игры становятся все сложнее, то поиск пути также эволюционирует и развивается вместе с ними.

Стратегии реального времени обычно содержат большие территории с открытым ландшафтом, в которых поиск пути обычно является простой задачей. Однако в большинстве случаев по карте перемещается не один юнит, а несколько, что создает потребность в различных и намного более сложных алгоритмах поиска пути для избежания пробок в узких областях игрового ландшафта. В стратегиях игровой уровень делится на тайлы (англ. tiles), которые действуют как узлы (англ. nodes) в алгоритме поиска пути .

В жанре 3D-шутеров используются намного более ограниченные пространства, которые не так легко разделить на узлы. Здесь взамен узлов используются так называемые waypoints (дословно с англ. — «точки пути»). Waypoints — это нерегулярные и вручную установленные узлы, которые содержат информацию о том, к каким другим узлам возможно добраться от данного.

Определение задачи

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

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

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

Существуют различные постановки задачи о кратчайшем пути:

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

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

Задача о кратчайшем пути с учетом дополнительных ограничений

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

1. Кратчайший путь, проходящий через заданное множество вершин. Можно рассматривать два ограничения: кратчайший путь должен проходить через выделенное множество вершин, и кратчайший путь должен содержать как можно меньше невыделенных вершин. Первое из них хорошо известна в теории исследования операций .
2. Минимальное покрытие вершин ориентированного графа путями. Осуществляется поиск минимального по числу путей покрытия графа, а именно подмножества всех s-t путей, таких что, каждая вершина ориентированного графа принадлежит хотя бы одному такому пути .
3. Задача о требуемых путях. Требуется найти минимальное по мощности множество s-t путей такое, что для любого найдется путь , накрывающий его. — множество некоторых путей в ориентированном графе G .
4. Минимальное покрытие дуг ориентированного графа путями. Задача состоит в отыскании минимального по числу путей подмножества всех путей, такого, что каждая дуга принадлежит хотя бы одному такому пути. При этом возможно дополнительное требование о том, чтобы все пути исходили из одной вершины .

алгоритмы поиска кратчайшего пути

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

К самым известным и популярным алгоритмам поиска пути относятся такие алгоритмы

• Алгоритм поиска A*
• Алгоритм Дейкстры
• Волновой алгоритм
• Маршрутные алгоритмы
• Навигационная сетка (Navmesh)
• Иерархические алгоритмы
• Обход препятствий
• Разделяй и властвуй
• Алгоритм поворота Креша

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

• Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без ребер отрицательного веса .
• Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.
• Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.
• Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа .
• Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
• Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах. Также используется для поиска кратчайшего расстояния на карте в стратегических играх.
• Поиск кратчайшего пути на основе алгоритма Килдала .

1) Задача о кратчайшем пути в заданный пункт назначения (single-destination shortest-paths problem). Требуется найти кратчайший путь в заданную вершину назначения (destination vertex) t, который начинается в каждой из вершин v. Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине.

2) Задача о кратчайшем пути между заданной парой вершин (single-pair shortest-paths problem). Требуется найти кратчайший путь из заданной вершины u в заданную вершину v. Если решена задача о заданной исходной вершине u, то эта задача тоже решается.

3) Задача о кратчайшем пути между всеми парами вершин (all-pairs shortest-paths problem). Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.

В работе (Черкасский и др., 1993) представлено еще несколько алгоритмов для решения этой задачи.

Задача поиска кратчайшего пути из одной вершины во все остальные

В такой постановке задачи осуществляется поиск кратчайшего пути из вершины v во все остальные вершины на графе.

Невзвешенный ориентированный граф

Алгоритм	Сложность	Автор
Поиск в ширину	O(E)

Ориентированный граф с неотрицательными весами

Алгоритм	Сложность	Автор
—	O(V2EL)	Форд 1956
Алгоритм Беллмана — Форда	O(VE)	Беллман 1958 , Мур 1957
—	O(V2 log V)	Данциг 1958, Данциг 1960, Minty (cf. Pollack&Wiebenson 1960), Whiting&Hillier 1960
Алгоритм Дейкстры со списком.	O(V2)	Leyzorek et al. 1957 , Дейкстра 1959
Алгоритм Дейкстры с модифицированной двоичной кучей	O((E + V) log V)	—
. . .	. . .	. . .
Алгоритм Дейкстры с использованием фибоначчиевой кучи	O(E + V log V)	Фридман&Тарьян 1984 , Фридман&Тарьян 1987
—	O(E log log L)	Джонсон 1982, Карлссон&Поблете 1983
Алгоритм Габова	O(E logE/V L)	Габов 1983, Габов 1985
—	O(E + V√log L)	Ахуджа et al. 1990

Ориентированный граф с произвольными весами

Алгоритм	Сложность	Автор
Алгоритм Беллмана — Форда	O(VE)	Беллман , Мур

Задача о кратчайшем пути между всеми парами вершин

Задача о кратчайшем пути между всеми парами вершин для невзвешенного ориентированного графа была поставлена Симбелом в 1953 году , который обнаружил, что она может быть решена за линейное количество манипуляций (умножения) с матрицей. Сложность такого алгоритма O(V⁴).

Так же для решения данной задачи существуют другие более быстрые алгоритмы, такие как Алгоритм Флойда — Уоршелла со сложностью O(V³), и Алгоритм Джонсона (является комбинацией алгоритмов Бэллмана-Форда и Дейкстры) со сложностью O(VE + V² log V).

Применение задач на поиск кретчайшего пути

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

Картографические сервисы

Алгоритмы нахождения кратчайшего пути на графе применяются для нахождения путей между физическими объектами на таких картографических сервисах, как карты Google или OpenStreetMap. В обучающем видео от Google можно узнать различные эффективные алгоритмы, которые применяются в данной сфере^[17].

Недетерминированная машина

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

Сети дорог

Задача поиска кратчайшего пути на графе широко используется при определении наименьшего расстояния в сети дорог.

Сеть дорог можно представить в виде графа с положительными весами. Вершины являются дорожными развязками, а ребра дорогами, которые их соединяют. Веса ребер могут соответствовать протяженности данного участка, времени необходимому для его преодоления или стоимости путешествия по нему. Ориентированные ребра можно использовать для представления односторонних улиц. В таком графе можно ввести характеристику, которая указывает на то, что одни дороги важнее других для длительных путешествий (например автомагистрали). Она была формализована в понятии (идее) о магистралях^[18].

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

1. этап предобработки. Производится предварительная обработка графа без учета начальной и конечной вершины (может длиться до нескольких дней, если работать с реальными данными). Обычно выполняется один раз и потом используются полученные данные.
2. этап запроса. Осуществляется запрос и поиск кратчайшего пути, при этом известны начальная и конечная вершина.

Самый быстрый алгоритм может решить данную задачу на дорогах Европы или Америки за доли микросекунды^[19].

Другие подходы (техники), которые применяются в данной сфере:

• ALT
• Arc Flags
• Contraction hierarchies
• Transit Node Routing
• Reach based Pruning
• Labeling

Похожие задачи

Существуют задачи, которые похожи на задачу поиска кратчайшего пути на графе.

• Поиск кратчайшего пути в вычислительной геометрии (см. евклидов кратчайший путь).
• Задача коммивояжера. Требуется найти кратчайший маршрут, проходящий через указанные города (вершины) хотя бы по одному разу с последующим возвратом в исходный город. Данная задача относится к классу NP-трудных задач в отличие от задачи поиска кратчайшего пути, которая может быть решена за полиномиальное время в графах без циклов. Задача коммивояжера решается неэффективно для больших наборов данных.
• Задача канадского путешественника и задача стохастического поиска кратчайшего пути являются обобщением рассматриваемой задачи, в которых обходимый граф заранее полностью неизвестен и изменяется во времени или следующий проход по графу вычисляется на основе вероятностей.
• Задача поиска кратчайшего пути, когда в графе происходят преобразования. Например, изменяется вес ребра или удаляется вершина^[20].

Постановка задачи линейного программирования

Пусть дан направленный граф (V, A), где V — множество вершин и A — множество ребер, с начальной вершиной обхода s, конечной t и весами w_ij для каждого ребра (i, j) в A. Вес каждого ребра соответствует переменной программы x_ij.

Тогда задача ставится следующим образом: найти минимум функции , где , при условии что для всех i и j выполняется следующее неравенство:

Вау!! 😲 Ты еще не читал? Это зря!

• Транспортная сеть
• Двунаправленный поиск
• сетевые модели алгоритм построения минимального остовного дерева алгоритм определения кратчайшего пути алгоритм флойда ,
• декомпозиция графов , пути в графах , кратчайшие пути ,
• алгоритм дейкстры , минимальное основное дерево ,
• алгоритм прима онлайн , минимальное остовное дерево , алгоритм прима , prim algorithm ,
• Алгоритм поиска A*
• Алгоритм Дейкстры
• Волновой алгоритм
• Маршрутные алгоритмы
• Навигационная сетка (Navmesh)
• Иерархические алгоритмы
• Обход препятствий
• Разделяй и властвуй
• Алгоритм поворота Креша
• Алгоритм Ли (волновой алгоритм )
• Поиск кратчайшего пути на основе алгоритма Килдала
• путь в теории графов ,

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

Зада́ча о кратча́йшем пути́ (англ. shortest path problem) — задача поиска самого короткого пути (цепи) между двумя точками (вершинами) на графе, в которой минимизируется сумма весов ребер, составляющих путь.

Кратчайшая (простая) цепь часто называется геодезической ^[1].

Задача о кратчайшем пути является одной из важнейших классических задач теории графов. Сегодня известно множество алгоритмов для её решения^[⇨].

У данной задачи существуют и другие названия: задача о минимальном пути или, в устаревшем варианте, задача о дилижансе.

Значимость данной задачи определяется её различными практическими применениями^[⇨]. Например в GPS-навигаторах, где осуществляется поиск кратчайшего пути между двумя перекрестками. В качестве вершин выступают перекрестки, а дороги являются ребрами, которые лежат между ними. Сумма расстояний всех дорог между перекрестками должна быть минимальной, тогда найден самый короткий путь.

Определение[править | править вики-текст]

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

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

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

Существуют различные постановки задачи о кратчайшем пути:

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

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

Задача о кратчайшем пути с учетом дополнительных ограничений[править | править вики-текст]

Задача о кратчайшем пути очень часто встречается в ситуации, когда необходимо учитывать дополнительные ограничения. Наличие их может значительно повысить сложность задачи^[2]. Примеры таких задач:

1. Кратчайший путь, проходящий через заданное множество вершин. Можно рассматривать два ограничения: кратчайший путь должен проходить через выделенное множество вершин, и кратчайший путь должен содержать как можно меньше невыделенных вершин. Первое из них хорошо известна в теории исследования операций^[3].
2. Минимальное покрытие вершин ориентированного графа путями. Осуществляется поиск минимального по числу путей покрытия графа, а именно подмножества всех s-t путей, таких что, каждая вершина ориентированного графа принадлежит хотя бы одному такому пути^[4].
3. Задача о требуемых путях. Требуется найти минимальное по мощности множество s-t путей такое, что для любого найдется путь , накрывающий его.  — множество некоторых путей в ориентированном графе G^[5].
4. Минимальное покрытие дуг ориентированного графа путями. Задача состоит в отыскании минимального по числу путей подмножества всех путей, такого, что каждая дуга принадлежит хотя бы одному такому пути. При этом возможно дополнительное требование о том, чтобы все пути исходили из одной вершины^[6].

Алгоритмы[править | править вики-текст]

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

• Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса^[7].
• Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.
• Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.
• Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа^[7].
• Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
• Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах. Так же используется для поиска кратчайшего расстояния на карте в стратегических играх.
• Поиск кратчайшего пути на основе алгоритма Килдала^[8].

В работе (Черкасский и др., 1993)^[9] представлено ещё несколько алгоритмов для решения этой задачи.

Задача поиска кратчайшего пути из одной вершины во все остальные[править | править вики-текст]

В такой постановке задачи осуществляется поиск кратчайшего пути из вершины v во все остальные вершины на графе.

Взвешенный ориентированный граф[править | править вики-текст]

Алгоритм	Сложность	Автор
Поиск в ширину	O(E)

Ориентированный граф с неотрицательными весами[править | править вики-текст]

Алгоритм	Сложность	Автор
—	O(V2EL)	Форд 1956
Алгоритм Беллмана — Форда	O(VE)	Беллман 1958[10], Мур 1959[11]
—	O(V2 log V)	Данциг 1958, Данциг 1960, Minty (cf. Pollack&Wiebenson 1960), Whiting&Hillier 1960
Алгоритм Дейкстры со списком.	O(V2)	Leyzorek et al. 1957[12], Дейкстра 1959[13]
Алгоритм Дейкстры с модифицированной двоичной кучей	O((E + V) log V)	—
. . .	. . .	. . .
Алгоритм Дейкстры с использованием фибоначчиевой кучи	O(E + V log V)	Фридман&Тарьян 1984[14], Фридман&Тарьян 1987[15]
—	O(E log log L)	Джонсон 1982, Карлссон&Поблете 1983
Алгоритм Габова	O(E logE/V L)	Габов 1983, Габов 1985
—	O(E + V√log L)	Ахуджа et al. 1990

Ориентированный граф с произвольными весами[править | править вики-текст]

Алгоритм	Сложность	Автор
Алгоритм Беллмана — Форда	O(VE)	Беллман[10], Мур[16]

Задача о кратчайшем пути между всеми парами вершин[править | править вики-текст]

Задача о кратчайшем пути между всеми парами вершин для невзвешенного ориентированного графа была поставлена Симбелом в 1953 году^[17], который обнаружил, что она может быть решена за линейное количество манипуляций (умножения) с матрицей. Сложность такого алгоритма O(V⁴).

Так же для решения данной задачи существуют другие более быстрые алгоритмы, такие как Алгоритм Флойда — Уоршелла со сложностью O(V³), и Алгоритм Джонсона (является комбинацией алгоритмов Бэллмана-Форда и Дейкстры) со сложностью O(VE + V² log V).

Применение[править | править вики-текст]

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

Картографические сервисы[править | править вики-текст]

Алгоритмы нахождения кратчайшего пути на графе применяются для нахождения путей между физическими объектами на таких картографических сервисах, как карты Google или OpenStreetMap. В обучающем видео от Google можно узнать различные эффективные алгоритмы, которые применяются в данной сфере^[19].

Недетерминированная машина[править | править вики-текст]

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

Сети дорог[править | править вики-текст]

Задача поиска кратчайшего пути на графе широко используется при определении наименьшего расстояния в сети дорог.

Сеть дорог можно представить в виде графа с положительными весами. Вершины являются дорожными развязками, а ребра дорогами, которые их соединяют. Веса ребер могут соответствовать протяженности данного участка, времени необходимому для его преодоления или стоимости путешествия по нему. Ориентированные ребра можно использовать для представления односторонних улиц. В таком графе можно ввести характеристику, которая указывает на то, что одни дороги важнее других для длительных путешествий (например автомагистрали). Она была формализована в понятии (идее) о магистралях^[20].

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

1. этап предобработки. Производится предварительная обработка графа без учета начальной и конечной вершины (может длиться до нескольких дней, если работать с реальными данными). Обычно выполняется один раз и потом используются полученные данные.
2. этап запроса. Осуществляется запрос и поиск кратчайшего пути, при этом известны начальная и конечная вершина.

Самый быстрый алгоритм может решить данную задачу на дорогах Европы или Америки за доли микросекунды^[21].

Другие подходы (техники), которые применяются в данной сфере:

• ALT
• Arc Flags
• Contraction hierarchies
• Transit Node Routing
• Reach based Pruning
• Labeling

Похожие задачи[править | править вики-текст]

Существуют задачи, которые похожи на задачу поиска кратчайшего пути на графе.

• Поиск кратчайшего пути в вычислительной геометрии (см. евклидов кратчайший путь).
• Задача коммивояжёра. Требуется найти кратчайший маршрут, проходящий через указанные города (вершины) хотя бы по одному разу с последующим возвратом в исходный город. Данная задача относится к классу NP-трудных задач в отличие от задачи поиска кратчайшего пути, которая может быть решена за полиномиальное время в графах без циклов. Задача коммивояжёра решается неэффективно для больших наборов данных.
• Задача канадского путешественника и задача стохастического поиска кратчайшего пути являются обобщением рассматриваемой задачи, в которых обходимый граф заранее полностью неизвестен и изменяется во времени или следующий проход по графу вычисляется на основе вероятностей.
• Задача поиска кратчайшего пути, когда в графе происходят преобразования. Например, изменяется вес ребра или удаляется вершина^[22].

Постановка задачи линейного программирования[править | править вики-текст]

Пусть дан направленный граф (V, A), где V — множество вершин и A — множество ребер, с начальной вершиной обхода s, конечной t и весами w_ij для каждого ребра (i, j) в A. Вес каждого ребра соответствует переменной программы x_ij.

Тогда задача ставится следующим образом: найти минимум функции , где , при условии что для всех i и j выполняется следующее неравенство:

См. также[править | править вики-текст]

• IEEE 802.1aq
• Транспортная сеть
• Двунаправленный поиск

Примечания[править | править вики-текст]

Литература[править | править вики-текст]

• Евстигнеев В. А. Глава 3. Итеративные алгоритмы глобального анализа графов. Пути и покрытия // Применение теории графов в программировании / Под ред. А. П. Ершова. — Москва: Наука. Главная редакция физико-математической литературы, 1985. — С. 138-150. — 352 с.
• Алексеев В.Е., Таланов В.А. Глава 3.4. Нахождения кратчайших путей в графе // Графы. Модели вычислений. Структуры данных. — Нижний Новгород: Издательство Нижегородского гос. университета, 2005. — С. 236-237. — 307 с. — ISBN 5–85747–810–8.
• Галкина В.А. Глава 4. Построение кратчайших путей в ориентированном графе // Дискретная математика. Комбинаторная оптимизация на графах. — Москва: Издательство «Гелиос АРВ», 2003. — С. 75-94. — 232 с. — ISBN 5–85438–069–2.
• Берж К. Глава 7. Задача о кратчайшем пути // Теория графов и её применения = Theorie des graphes et ses applications / Под ред. И. А. Вайнштейна. — Москва: Издательство иностранной литературы, 1962. — С. 75-81. — 320 с.
• Ойстин Оре. Теория графов / Под ред. И. М. Овчинниковой. — Издательство наука, 1980. — 336 с.
• Cherkassky Boris V.,Goldberg Andrew V. , Radzik Tomasz. Shortest paths algorithms: theory and experimental evaluation (англ.) // Mathematical Programming. — 1996. — No. 73. — P. 129–174. — DOI:10.1016/0025-5610(95)00021-6.

• Харари Ф. Глава 2. Графы // Теория графов / Под ред. Г. П. Гаврилова. — Издательство мир, 1973. — С. 27. — 300 с. — ISBN 5-354-00301-6.
• Ричард Беллман (1958). «On a routing problem». Quarterly of Applied Mathematics 16: 87–90.

• Dijkstra E. W. A note on two problems in connexion with graphs // Numer. Math — Springer Science+Business Media, 1959. — Vol. 1, Iss. 1. — P. 269—271. — ISSN 0029-599X; 0945-3245 — doi:10.1007/BF01386390
• E. F. Moore (April 2–5, 195). «The shortest path through a maze» (Harvard University Press): 285–292.
• M. Leyzorek, R. S. Gray, A. A. Gray, W. C. Ladew, S. R. Meaker, R. M. Petry, R. N. Seitz. Investigation of Model Techniques — First Annual Report — 6 June 1956 — 1 July 1957 — A Study of Model Techniques for Communication Systems. — Cleveland, Ohio: Case Institute of Technology, 1957.
• Michael Fredman Lawrence, Роберт Андре Тарьян (1984). «Fibonacci heaps and their uses in improved network optimization algorithms» (IEEE): 338–346. DOI:10.1109/SFCS.1984.715934.
• Michael Fredman Lawrence, Роберт Андре Тарьян (1987). «Fibonacci heaps and their uses in improved network optimization algorithms». Journal of the Association for Computing Machinery 34 (3): 596–615. DOI:10.1145/28869.28874.
• Shimbel, Alfonso (1953). «Structural parameters of communication networks». Bulletin of Mathematical Biophysics 15 (4): 501–507. DOI:10.1007/BF02476438.
• Sanders, Peter (March 23, 2009). «Fast route planning» (Google Tech Talk).
• Chen, Danny Z. (December 1996). «Developing algorithms and software for geometric path planning problems». ACM Computing Surveys 28 (4es): 18. DOI:10.1145/242224.242246.
• Abraham, Ittai; Fiat, Amos; Goldberg, Andrew V.; Werneck, Renato F. (2010). «Highway Dimension, Shortest Paths, and Provably Efficient Algorithms». ACM-SIAM Symposium on Discrete Algorithms: 782-793.
• Abraham, Ittai; Delling, Daniel; Goldberg, Andrew V.; Werneck, Renato F. (2011). «A Hub-Based Labeling Algorithm for Shortest Paths on Road Networks. Symposium on Experimental Algorithms]»: 230-241.
• Kroger, Martin (2005). «Shortest multiple disconnected path for the analysis of entanglements in two- and three-dimensional polymeric systems». Computer Physics Communications 168 (168): 209–232. DOI:10.1016/j.cpc.2005.01.020.
• Ladyzhensky Y., Popoff Y. (2006). «Algorithm to define the shortest paths between all nodes in a graph after compressing of two nodes. Proceedings of Donetsk national technical university, Computing and automation. Vol.107. Donetsk»: 68–75.

Кратчайшие пути в графах. BFS. Dijkstra.

Задача

Дан ориентированный граф $G = (V, E)$, а также вершина $s$.
Найти длину кратчайшего пути от $s$ до каждой из вершин графа. Длина пути — количество рёбер в нём.

BFS

BFS — breadth-first search, или же поиск в ширину.

Этот алгоритм позволяет решать следующую задачу.

Алгоритм работает следующим образом.

1. Создадим массив $dist$ расстояний. Изначально $dist[s] = 0$ (поскольку расстояний от вершины до самой себя равно $0$) и $dist[v] = infty$ для $v neq s$.
2. Создадим очередь $q$. Изначально в $q$ добавим вершину $s$.
3. Пока очередь $q$ непуста, делаем следующее:
   1. Извлекаем вершину $v$ из очереди.
   2. Рассматриваем все рёбра $(v, u) in E$. Для каждого такого ребра пытаемся сделать релаксацию: если $dist[v] + 1 < dist[u]$, то мы делаем присвоение $dist[u] = dist[v] + 1$ и добавляем вершину $u$ в очередь.

Визуализации:

• https://visualgo.net/mn/dfsbfs

• https://www.hackerearth.com/practice/algorithms/graphs/breadth-first-search/visualize/

Интуитивное понимание алгоритма

Можно представить, что мы поджигаем вершину $s$. Каждый шаг алгоритма — это распространение огня на соседние вершины. Понятно, что огонь доберётся до вершины по кратчайшему пути.

Заметьте, что этот алгоритм очень похож на DFS — достаточно заменить очередь на стек и поиск в ширину станет поиском в глубину. Действительно, оба алгоритма при обработке вершины просто записывают всех непосещенных соседей, в которые из неё есть ребро, в структуру данных, и после этого выбирает следующую вершину для обработки в структуре данных. В DFS это стек (благодаря рекурсии), поэтому мы сначала записываем соседа, идем в обрабатываем его полностью, а потом начинаем обрабатывать следующего соседа. В BFS это очередь, поэтому мы кидаем сразу всех соседей, а потом начинаем обрабатывать вообще другую вершину — ту непосещенную, которую мы положили в очередь раньше всего.

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

• поиск компонент связности
• проверка графа на двудольность
• построение остова

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

n — количество вершин в графе; adj — список смежности

vector<int> bfs(int s) {
    // длина любого кратчайшего пути не превосходит n - 1,
    // поэтому n - достаточное значение для "бесконечности";
    // после работы алгоритма dist[v] = n, если v недостижима из s
    vector<int> dist(n, n);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }

    return dist;
}

Свойства кратчайших путей

Обозначение: $d(v)$ — длина кратчайшего пути от $s$ до $v$.

Лемма 1.

Пусть $(u, v) in E$, тогда $d(v) leq d(u) + 1$.

Действительно, существует путь из $s$ в $u$ длины $d(u)$, а также есть ребро $(u, v)$, следовательно, существует путь из $s$ в $v$ длины $d(u) + 1$. А значит кратчайший путь из $s$ в $v$ имеет длину не более $d(u) + 1$,

Лемма 2.

Рассмотрим кратчайший путь от $s$ до $v$. Обозначим его как $u_1, u_2, dots u_k$ ($u_1 = s$ и $u_k = v$, а также $k = d(v) + 1$).
Тогда $forall (i < k): d(u_i) + 1 = d(u_{i + 1})$.

Действительно, пусть для какого-то $i < k$ это не так. Тогда, используя лемму 1, имеем: $d(u_i) + 1 > d(u_{i + 1})$. Тогда мы можем заменить первые $i + 1$ вершин пути на вершины из кратчайшего пути из $s$ в $u_{i + 1}$. Полученный путь стал короче, но мы рассматривали кратчайший путь — противоречие.

Корректность

Утверждение.

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

Докажем это по индукции по количеству итераций алгоритма (итерация — извлечение вершины из очереди и дальнейшая релаксация).

База очевидна.
Переход. Сначала докажем первую часть. Предположим, что $dist[v] + 1 < dist[u]$, но $dist[v] + 1$ — некорректное расстояние до вершины $u$, то есть $dist[v] + 1 neq d(u)$. Тогда по лемме 1: $d(u) < dist[v] + 1$. Рассмотрим предпоследнюю вершину $w$ на кратчайшем пути от $s$ до $u$. Тогда по лемме 2: $d(w) + 1 = d(u)$. Следовательно, $d(w) + 1 < dist[v] + 1$ и $d(w) < dist[v]$. Но тогда по предположению индукции $w$ была извлечена раньше $v$, следовательно, при релаксации из неё в очередь должна была быть добавлена вершина $u$ с уже корректным расстоянием. Противоречие.
Теперь докажем вторую часть. По предположению индукции в очереди лежали некоторые вершины $u_1, u_2, dots u_k$, для которых выполнялось следующее: $dist[u_1] leq dist[u_2] leq dots leq dist[u_k]$ и $dist[u_k] — dist[u_1] leq 1$. Мы извлекли вершину $v = u_1$ и могли добавить в конец очереди какие-то вершины с расстоянием $dist[v] + 1$. Если $k = 1$, то утверждение очевидно. В противном случае имеем $dist[u_k] — dist[u_1] leq 1 leftrightarrow dist[u_k] — dist[v] leq 1 leftrightarrow dist[u_k] leq dist[v] + 1$, то есть упорядоченность сохранилась. Осталось показать, что $(dist[v] + 1) — dist[u_2] leq 1$, но это равносильно $dist[v] leq dist[u_2]$, что, как мы знаем, верно.

Время работы

Из доказанного следует, что каждая достижимая из $s$ вершина будет добавлена в очередь ровно $1$ раз, недостижимые вершины добавлены не будут. Каждое ребро, соединяющее достижимые вершины, будет рассмотрено ровно $2$ раза. Таким образом, алгоритм работает за $O(V+ E)$ времени, при условии, что граф хранится в виде списка смежности.

Неориентированные графы

Если дан неориентированный граф, его можно рассматривать как ориентированный граф с двумя обратными друг другу ориентированными рёбрами.

Восстановление пути

Пусть теперь заданы 2 вершины $s$ и $t$, и необходимо не только найти длину кратчайшего пути из $s$ в $t$, но и восстановить какой-нибудь из кратчайших путей между ними. Всё ещё можно воспользоваться алгоритмом BFS, но необходимо ещё и поддерживать массив предков $p$, в котором для каждой вершины будет храниться предыдущая вершина на кратчайшем пути.

Поддерживать этот массив просто: при релаксации нужно просто запоминать, из какой вершины мы прорелаксировали в данную. Также будем считать, что $p[s] = -1$: у стартовой вершины предок — некоторая несуществующая вершина.

Восстановление пути делается с конца. Мы знаем последнюю вершину пути — это $t$. Далее, мы сводим задачу к меньшей, переходя к нахождению пути из $s$ в $p[t]$.

Реализация BFS с восстановлением пути

// теперь bfs принимает 2 вершины, между которыми ищется пути
// bfs возвращает кратчайший путь из s в t, или же пустой vector, если пути нет
vector<int> bfs(int s, int t) {
    vector<int> dist(n, n);
    vector<int> p(n, -1);
    dist[s] = 0;
    queue<int> q;
    q.push(s);

    while (!q.empty()) {
        int v = q.front();
        q.pop();
        for (int u : adj[v]) {
            if (dist[u] > dist[v] + 1) {
                p[u] = v;
                dist[u] = dist[v] + 1;
                q.push(u);
            }
        }
    }
    
    // если пути не существует, возвращаем пустой vector
    if (dist[t] == n) {
        return {};
    }

    vector<int> path;
    while (t != -1) {
        path.push_back(t);
        t = p[t];
    }
    
    // путь был рассмотрен в обратном порядке, поэтому его нужно перевернуть
    reverse(path.begin(), path.end());
    return path;
}

Проверка принадлежности вершины кратчайшему пути

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

Запустим из вершины $s$ в графе $G$ BFS — найдём расстояния $d_1$. Построим транспонированный граф $G^T$ — граф, в котором каждое ребро заменено на противоположное. Запустим из вершины $t$ в графе $G^T$ BFS — найдём расстояния $d_2$.

Теперь очевидно, что $v$ принадлежит хотя бы одному кратчайшему пути из $s$ в $t$ тогда и только тогда, когда $d_1(v) + d_2(v) = d_1(t)$ — это значит, что есть путь из $s$ в $v$ длины $d_1(v)$, а затем есть путь из $v$ в $t$ длины $d_2(v)$, и их суммарная длина совпадает с длиной кратчайшего пути из $s$ в $t$.

Кратчайший цикл в ориентированном графе

Найти цикл минимальной длины в ориентированном графе.

Попытаемся из каждой вершины найти кратчайший цикл, проходящий через неё, с помощью BFS. Это делается аналогично обычному BFS: мы должны найти расстояний от вершины до самой себя, при этом не считая, что оно равно $0$.

Итого, у нас $|V|$ запусков BFS, и каждый запуск работает за $O(|V| + |E|)$. Тогда общее время работы составляет $O(|V|^2 + |V| |E|)$. Если инициализировать массив $dist$ единожды, а после каждого запуска BFS возвращать исходные значения только для достижимых вершин, решение будет работать за $O(|V||E|)$.

Задача

Дан взвешенный ориентированный граф $G = (V, E)$, а также вершина $s$. Длина ребра $(u, v)$ равна $w(u, v)$. Длины всех рёбер неотрицательные.
Найти длину кратчайшего пути от $s$ до каждой из вершин графа. Длина пути — сумма длин рёбер в нём.

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

Алгоритм Дейкстры решает приведённую выше задачу. Он работает следующим образом.

1. Создать массив $dist$ расстояний. Изначально $dist[s] = 0$ и $dist[v] = infty$ для $v neq s$.
2. Создать булёв массив $used$, $used[v] = 0$ для всех вершин $v$ — в нём мы будем отмечать, совершалась ли релаксация из вершины.
3. Пока существует вершина $v$ такая, что $used[v] = 0$ и $dist[v] neq infty$, притом, если таких вершин несколько, то $v$ — вершина с минимальным $dist[v]$, делать следующее:
   1. Пометить, что мы совершали релаксацию из вершины $v$, то есть присвоить $used[v] = 1$.
   2. Рассматриваем все рёбра $(v, u) in E$. Для каждого ребра пытаемся сделать релаксацию: если $dist[v] + w(v, u) < dist[u]$, присвоить $dist[u] = dist[v] + w(v, u)$.

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

Посчитаем, за сколько работает алгоритм. Мы $V$ раз ищем вершину минимальным $dist$, поиск минимума у нас линейный за $O(V)$, отсюда $O(V^2)$. Обработка ребер у нас происходит суммарно за $O(E)$, потому что на каждое ребро мы тратим $O(1)$ действий. Так мы находим финальную асимптотику: $O(V^2 + E)$.

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

Рёбра будем хранить как pair<int, int>, где первое число пары — куда оно ведёт; а второе — длина ребра.

// INF - infinity - бесконечность
const long long INF = (long long) 1e18 + 1;

vector<long long> dijkstra(int s) {
    vector<long long> dist(n, INF);
    dist[s] = 0;
    vector<bool> used(n);
    
    while (true) {
        // находим вершину, из которой будем релаксировать
        int v = -1;
        for (int i = 0; i < n; i++) {
            if (!used[i] && (v == -1 || dist[i] < dist[v])) {
                v = i;
            }
        }
        
        // если не нашли подходящую вершину, прекращаем работу алгоритма
        if (v == -1) {
            break;
        }
        
        for (auto &e : adj[v]) {
            int u = e.first;
            int len = e.second;
            if (dist[u] > dist[v] + len) {
                dist[u] = dist[v] + len;
            }
        }
    }
    
    return dist;
}

Восстановление пути

Восстановление пути в алгоритме Дейкстры делается аналогично восстановлению пути в BFS (и любой динамике).

Дейкстра на сете

Искать вершину с минимальным $dist$ можно гораздо быстрее, используя такую структуру данных как очередь с приоритетом. Нам нужно хранить пары $(dist, index)$ и уметь делать такие операции:

• Извлечь минимум (чтобы обработать новую вершину)
• Удалить вершину по индексу (чтобы уменьшить $dist$ до какого-то соседа)
• Добавить новую вершину (чтобы уменьшить $dist$ до какого-то соседа)

Для этого используют, например, кучу или сет. Удобно помимо сета хранить сам массив dist, который его дублирует, но хранит элементы по порядку. Тогда, чтобы заменить значение $(dist_1, u)$ на $(dist_2, u)$, нужно удалить из сета значение $(dist[u], u)$, сделать $dist[u] = dist_2;$ и добавить в сет $(dist[u], u)$.

Данный алгоритм будет работать за $V O(log V)$ извлечений минимума и $O(E log V)$ операций уменьшения расстояния до вершины (может быть сделано после каждого ребра). Поэтому алгоритм работает за $O(E log V)$.

Заметьте, что этот алгоритм не лучше и не хуже, чем без сета, который работает за $O(V^2 + E)$. Ведь если $E = O(V^2)$ (граф почти полный), то Дейкстра без сета работает быстрее, а если, наример, $E = O(V)$, то Дейкстра на сете работает быстрее. Учитывайте это, когда выбираете алгоритм.