Алгоритм Дейкстры: различия между версиями

Материал из Олимпиадное программирование в УлГТУ
Перейти к навигации Перейти к поиску
Нет описания правки
 
(не показано 14 промежуточных версий этого же участника)
Строка 1: Строка 1:
== TLDR ==
<youtube width="300" height="180">fA_xvuqzuGs</youtube>
<youtube width="300" height="180">J-7MzbEtTR0</youtube>
== Общие сведения ==
== Общие сведения ==
Дан ориентированный или неориентированный взвешенный граф; веса всех рёбер неотрицательны. Требуется определить кратчайшие расстояния из данной вершины до всех остальных.
Дан ориентированный или неориентированный взвешенный граф; веса всех рёбер неотрицательны. Требуется определить кратчайшие расстояния из данной вершины до всех остальных.


Пусть изначально расстояние до стартовой вершины равно нулю, расстояния до всех остальных вершин &mdash; бесконечности. Определим ближайшую вершину (на первом шаге таковой будет стартовая вершина). Как будет показано ниже, расстояние до выбранной вершины является кратчайшим и в дальнейшем не изменяется, поэтому его можно использовать для пересчёта расстояний до соседних вершин.
Пусть изначально расстояние до стартовой вершины равно нулю, расстояния до всех остальных вершин бесконечности. Определим ближайшую вершину (на первом шаге таковой будет стартовая вершина). Как будет показано ниже, расстояние до выбранной вершины является кратчайшим и в дальнейшем не изменяется, поэтому его можно использовать для пересчёта расстояний до соседних вершин.


Итак, пусть v &mdash; текущая ближайшая вершина и существует ребро v&rarr;u веса w. Обозначим кратчайшее расстояние до вершины v как dist[v], текущее расстояние до вершины u &mdash; dist[u]. Тогда если (dist[v] + w) < dist[u], то мы нашли более короткий путь к вершине u &mdash; он проходит через вершину v и ребро v&rarr;u. Соответственно, мы можем обновить значение dist[u]. Такое обновление называется релаксацией.
Итак, пусть v текущая ближайшая вершина и существует ребро v → to веса w. Обозначим кратчайшее расстояние до вершины v как dist[v], текущее расстояние до вершины to — dist[to]. Тогда если (dist[v] + w) < dist[to], то мы нашли более короткий путь к вершине to — он проходит через вершину v и ребро v → to. Следовательно, мы можем обновить значение dist[to]. Такое обновление называется релаксацией.


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


[[Файл:Dijkstra_proof.png|thumb|right|360px|Доказательство корректности алгоритма Дейкстры]]
[[Файл:Dijkstra_proof.png|thumb|right|360px|Доказательство корректности алгоритма Дейкстры]]
Доказательство того факта, что на каждой итерации расстояние до обрабатываемой вершины действительно является кратчайшим, проводится по индукции. Для базового случая (обрабатывается стартовая вершина, расстояние до неё равно нулю) утверждение выполняется. Далее, пусть утверждение выполняется для всех обработанных вершин (значения dist[] для них рассчитаны верно), а на текущем шаге выбрана вершина v. Обозначим через u первую необработанную вершину на кратчайшем пути до v, через t &mdash; вершину, предшествующую u на этом пути. Кратчайшее расстояние до вершины u равно сумме dist[t] и веса ребра t&rarr;u; эта сумма уже была записана в dist[u] при проведении релаксаций из вершины t, следовательно, значение dist[u] действительно равно кратчайшему расстоянию до вершины u. Далее, заметим, что должны выполняться условия dist[v] &le; dist[u] (так как вершина v является ближайшей на текущем шаге) и dist[v] &ge; dist[u] (так как u лежит на пути до v, а граф не содержит рёбер отрицательного веса). Отсюда dist[v] = dist[u], то есть в момент выбора вершины v значение dist[v] действительно равно кратчайшему расстоянию до неё.
Доказательство того факта, что на каждой итерации расстояние до обрабатываемой вершины действительно является кратчайшим, проводится по индукции. Для базового случая (обрабатывается стартовая вершина, расстояние до неё равно нулю) утверждение выполняется. Далее, пусть утверждение выполняется для всех обработанных вершин (значения dist[] для них рассчитаны верно), а на текущем шаге выбрана вершина v. Обозначим через u первую необработанную вершину на кратчайшем пути до v, через t &mdash; вершину, предшествующую u на этом пути. Кратчайшее расстояние до вершины u равно сумме dist[t] и веса ребра t u; эта сумма уже была записана в dist[u] при проведении релаксаций из вершины t, следовательно, значение dist[u] действительно равно кратчайшему расстоянию до вершины u. Далее, заметим, что должны выполняться условия dist[v] &le; dist[u] (так как вершина v является ближайшей на текущем шаге) и dist[v] &ge; dist[u] (так как u лежит на пути до v, а граф не содержит рёбер отрицательного веса). Отсюда dist[v] = dist[u], то есть в момент выбора вершины v значение dist[v] действительно равно кратчайшему расстоянию до неё.


== Демонстрация работы ==
== Демонстрация работы ==
Строка 17: Строка 21:
== Реализация для плотных графов ==
== Реализация для плотных графов ==


Здесь и далее будем считать, что граф задан списками смежности, а количество вершин равно <tt>N</tt>.
Здесь и далее будем считать, что граф задан списками смежности, а количество вершин равно <tt>vertexCount</tt>.
   
   
const int N = 1000;
 
  struct Edge {
  struct Edge {
     int vFrom, vTo;
     int to, weight;
    int weight;
  };
  };
  vector<Edge> g[N];
  vector<vector<Edge>> graph(vertexCount);


Алгоритм принимает индекс стартовой вершины <tt>vStart</tt> и заполняет глобальный массив <tt>dist[]</tt>. Роль значения &laquo;бесконечность&laquo; выполняет достаточно большая константа <tt>INF</tt>; её значение должно быть больше максимального возможного расстояния между вершинами, но не допускать переполнения при проведении релаксаций (для избежания переполнений также можно ввести в основной цикл контрольное условие: если расстояние до ближайшей вершины равно <tt>INF</tt>, выполнение алгоритма завершается). Логический массив <tt>used[]</tt> предназначен для отметки обработанных вершин.
Алгоритм принимает индекс стартовой вершины <tt>start</tt> и заполняет массив <tt>dist</tt>. Роль значения «бесконечность» выполняет достаточно большая константа <tt>INF</tt>; её значение должно быть больше максимального возможного расстояния между вершинами, но не допускать переполнения при проведении релаксаций (для избежания переполнений также можно ввести в основной цикл контрольное условие: если расстояние до ближайшей вершины равно <tt>INF</tt>, выполнение алгоритма завершается). Логический массив <tt>visited</tt> предназначен для отметки обработанных вершин.


После начальной инициализации <tt>used[]</tt> и <tt>dist[]</tt> производится <tt>N</tt> итераций алгоритма, на каждой из которых сначала определяется ближайшая из необработанных вершин (используется наивный поиск минимума с асимптотикой O(V)), затем выбранная вершина помечается как обработанная и производится попытка релаксации для каждого исходящего из неё ребра.
После начальной инициализации <tt>visited</tt> и <tt>dist</tt> производится <tt>vertexCount</tt> итераций алгоритма, на каждой из которых сначала определяется ближайшая из необработанных вершин (используется наивный поиск минимума с асимптотикой O(V)), затем выбранная вершина помечается как обработанная и производится попытка релаксации для каждого исходящего из неё ребра.


Хотя на каждой итерации выполняется различное число попыток релаксации, общее их количество равно E, так как будет просмотрено каждое ребро (один раз, если рёбра направленные, дважды &mdash; если ненаправленные). Таким образом, общая асимптотическая оценка алгоритма равна O(V<sup>2</sup> + E).
Хотя на каждой итерации выполняется различное число попыток релаксации, общее их количество равно E, так как будет просмотрено каждое ребро (один раз, если рёбра направленные, дважды если ненаправленные). Таким образом, общая асимптотическая оценка алгоритма равна O(V<sup>2</sup> + E).


  const int INF = 1 << 30;
  const int INF = 1e9;
int dist[N];
bool used[N];
vector<int> dijkstra(vector<vector<Edge>> &graph, int start) {
    vector<bool> visited(graph.size());
    vector<int> dist(graph.size(), INF);
    dist[start] = 0;
   
   
void dijkstra(int vStart) {
     for (int i = 0; i < graph.size(); i++) {
     for (int i = 0; i < N; i++) {
         int nearestV = -1;
        used[i] = false;
         for (int v = 0; v < graph.size(); v++)
        dist[i] = INF;
             if (!visited[v] && (nearestV == -1 || dist[v] < dist[nearestV]))
    }
                 nearestV = v;
    dist[vStart] = 0;
   
         visited[nearestV] = true;
    for (int i = 0; i < N; i++) {
         int v = -1;
         for (auto &[to, weight] : graph[nearestV])
         for (int j = 0; j < N; j++)
             if (dist[to] > dist[nearestV] + weight)
             if (!used[j] && (v == -1 || dist[j] < dist[v]))
                 dist[to] = dist[nearestV] + weight;
                 v = j;
         used[v] = true;
         for (int j = 0; j < g[v].size(); j++) {
            int u = g[v][j].vTo;
            int w = g[v][j].weight;
             if (dist[u] > dist[v] + w)
                 dist[u] = dist[v] + w;
        }             
     }
     }
    return dist;
  }
  }


== Реализация для разреженных графов ==
== Реализация для разреженных графов ==


Алгоритм Дейкстры выполняет O(V) поисков ближайшей вершины и O(E) релаксаций. В предыдущей реализации информация о расстоянии до вершин хранилась в массиве, что позволяло производить операции первого типа за O(V), второго типа &mdash; за O(1). Итоговая оценка O(V<sup>2</sup> + E) является неудовлетворительной для разреженных графов (в которых E << V<sup>2</sup>). Поэтому в данном случае имеет смысл использовать структуры данных, позволяющие производить и поиск минимума, и обновление элементов с асимптотикой O(logV).
Алгоритм Дейкстры выполняет O(V) поисков ближайшей вершины и O(E) релаксаций. В предыдущей реализации информация о расстоянии до вершин хранилась в массиве, что позволяло производить операции первого типа за O(V), второго типа за O(1). Итоговая оценка O(V<sup>2</sup> + E) является неудовлетворительной для разреженных графов (в которых E << V<sup>2</sup>). Поэтому в данном случае имеет смысл использовать структуры данных, позволяющие производить и поиск минимума, и обновление элементов с асимптотикой O(logV).


Одной из таких структур является [[Множество и словарь. Реализация на деревьях поиска|сбалансированное двоичное дерево поиска]], представленное в STL контейнером <tt>set</tt>. Так как требуется упорядочить вершины согласно расстоянию до них, будем хранить множество <tt>s</tt> из пар (расстояние, индекс вершины). Пары STL сравниваются начиная с первого поля, что обеспечит нужный порядок. Множество <tt>s</tt> также будет выполнять функции массива <tt>used[]</tt>, так как в него будут помещаться только необработанные вершины.
Одной из таких структур является [[Множество и словарь. Реализация на деревьях поиска|сбалансированное двоичное дерево поиска]], представленное в STL контейнером <tt>set</tt>. Так как требуется упорядочить вершины согласно расстоянию до них, будем хранить множество <tt>unvisited</tt> из пар (расстояние, индекс вершины). Пары STL сравниваются начиная с первого поля, что обеспечит нужный порядок. Множество <tt>unvisited</tt> также будет выполнять функции массива <tt>used</tt>, так как в него будут помещаться только необработанные вершины.


Теперь для определения ближайшей вершины достаточно обратиться к полю <tt>s.begin()</tt>. При проведении релаксации нужно предварительно удалить из множества пару со старым расстоянием (если она там была), а затем добавить пару с обновлённым расстоянием.
Теперь для определения ближайшей вершины достаточно обратиться к полю <tt>unvisited.begin()</tt>. При проведении релаксации нужно предварительно удалить из множества пару со старым расстоянием (если она там была), а затем добавить пару с обновлённым расстоянием.


Итоговая асимптотика данной реализации составляет O((V + E)logV), что в большинстве случаев сводится к O(ElogV). Следует обратить внимание на то, что для плотных графов (в которых E &asymp; V<sup>2</sup>) эта реализация оказывается медленнее предыдущей.
Итоговая асимптотика данной реализации составляет O((V + E)logV), что в большинстве случаев сводится к O(ElogV). Следует обратить внимание на то, что для плотных графов (в которых E &asymp; V<sup>2</sup>) эта реализация оказывается медленнее предыдущей.


  const int INF = 1 << 30;
  const int INF = 1e9;
int dist[N];
set< pair<int, int> > s;
   
   
  void dijkstra(int vStart) {
  vector<int> dijkstra(vector<vector<Edge>> &graph, int start) {
     for (int i = 0; i < N; i++)
     vector<int> dist(graph.size(), INF);
        dist[i] = INF;
    set<pair<int, int>> unvisited;
     dist[vStart] = 0;
     dist[start] = 0;
     s.insert(make_pair(dist[vStart], vStart));
     unvisited.insert({ dist[start], start });
   
     while (!s.empty()) {
     while (!unvisited.empty()) {
         int v = s.begin()->second;
         int nearestV = unvisited.begin()->second;
         s.erase(s.begin());
         unvisited.erase(unvisited.begin());
         for (int j = 0; j < g[v].size(); j++) {
            int u = g[v][j].vTo;
         for (auto &[to, weight] : graph[nearestV]) {
            int w = g[v][j].weight;
             if (dist[to] > dist[nearestV] + weight) {
             if (dist[u] > dist[v] + w) {
                 unvisited.erase({ dist[to], to });
                 s.erase(make_pair(dist[u], u));
                 dist[to] = dist[nearestV] + weight;
                 dist[u] = dist[v] + w;
                 unvisited.insert({ dist[to], to });
                 s.insert(make_pair(dist[u], u));
             }
             }
         }            
         }
     }
     }
    return dist;
  }
  }


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


Если в задаче требуется выводить сами кратчайшие пути, то нужно поддерживать массив предков <tt>parent[]</tt>: ячейка <tt>parent[i]</tt> содержит индекс непосредственного предка вершины <tt>i</tt> на кратчайшем пути от стартовой вершины до <tt>i</tt>. Изначально предок каждой вершины не определён, что помечается значением -1; обновление предка происходит вместе с обновлением кратчайшего расстояния при успешной релаксации.
Если в задаче требуется выводить сами кратчайшие пути, то нужно поддерживать массив предков <tt>from</tt>: ячейка <tt>from[v]</tt> содержит индекс непосредственного предка вершины <tt>v</tt> на кратчайшем пути от стартовой вершины до <tt>v</tt>. Изначально предок каждой вершины не определён, что помечается значением -1; обновление предка происходит вместе с обновлением кратчайшего расстояния при успешной релаксации.


После завершения работы алгоритма можно восстановить кратчайший путь от начальной вершины до некоторой достижимой вершины v в обратном порядке, последовательно перемещаясь от v по массиву <tt>parent[]</tt>, пока предок текущей вершины не станет равным -1 (это будет означать, что мы оказались в начальной вершине). Вывести путь в естественном виде можно с помощью стека.
После завершения работы алгоритма можно восстановить кратчайший путь от начальной вершины до некоторой достижимой вершины finish в обратном порядке, последовательно перемещаясь по массиву <tt>from</tt>, пока текущая вершина не станет равной -1. В конце нужно развернуть получившуюся последовательность вершин.


{| width="100%"
{| width="100%"
| width="50%"  |
| width="50%"  |
  int parent[N];
  vector<int> from(n, -1);
   
   
  void dijkstra(int vStart) {
  if (dist[to] > dist[nearestV] + weight) {             
    for (int i = 0; i < N; i++)
    dist[to] = dist[nearestV] + weight;
        parent[i] = -1;
    from[to] = nearestV;           
    //...   
            if (dist[u] > dist[v] + w) {             
                dist[u] = dist[v] + w;
                parent[u] = v;           
            }
    //...
  }
  }
| width="10px" | &nbsp;
| width="10px" | &nbsp;
| width="50%"  |
| width="50%"  |
  stack<int> path;
  vector<int> path;
   
   
  int currentVertex = v;
  for (int v = finish; v != -1; v = from[v])
do {
     path.push_back(v);
     path.push(currentVertex);
    currentVertex = parent[currentVertex];
} while (currentVertex != -1);
   
   
  while (!path.empty()) {
  reverse(path.begin(), path.end());
    printf("%d ", path.top());
    path.pop();
}
|}
|}


Если в графе присутствуют кратные рёбра между одной и той же парой вершин, то логику определения кратчайшего пути придётся усложнить. В данных условиях можно явно сохранить все рёбра графа в отдельном массиве, а в массив <tt>parent[]</tt> записывать индекс того ребра, по которому осуществлялась релаксация. При этом можно изменить представление графа: вместо хранения списка смежных рёбер для каждой вершины (<tt>vector<Edge> g[]</tt>) можно хранить список индексов этих рёбер в массиве рёбер (<tt>vector<int> g[]</tt>).
Если в графе присутствуют кратные рёбра между одной и той же парой вершин, то логику определения кратчайшего пути придётся усложнить. В данных условиях можно явно сохранить все рёбра графа в отдельном массиве, а в массив <tt>parent</tt> записывать индекс того ребра, по которому осуществлялась релаксация. При этом можно изменить представление графа: вместо хранения списка смежных рёбер для каждой вершины (<tt>vector<vector<Edge>> graph</tt>) можно хранить список индексов этих рёбер в массиве рёбер (<tt>vector<vector<int>> graph</tt>).
 
== Ссылки на задачи ==


* [http://acmp.ru/?main=task&id_task=132 ACMP #132 &mdash; Алгоритм Дейкстры]
== Ссылки ==
* [http://acmp.ru/?main=task&id_task=133 ACMP #133 &mdash; Заправки]
Теория:
* [http://acmp.ru/?main=task&id_task=134 ACMP #134 &mdash; Автобусы]
* e-maxx.ru — [http://e-maxx.ru/algo/dijkstra Алгоритм Дейкстры за O(N<sup>2</sup> + M)], [http://e-maxx.ru/algo/dijkstra_sparse Алгоритм Дейкстры за O(MlogN)]
* [http://acmp.ru/?main=task&id_task=469 ACMP #469 &mdash; Химическая тревога]
* cp-algorithms.com — [https://cp-algorithms.com/graph/dijkstra.html Dijkstra Algorithm], [https://cp-algorithms.com/graph/dijkstra_sparse.html Dijkstra Algorithm for sparse graphs]
* [https://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B neerc.ifmo.ru/wiki — Алгоритм Дейкстры]
* [https://brestprog.by/topics/dijkstra/ brestprog.by — Взвешенные графы. Алгоритм Дейкстры]
* algorithmica.org — [http://algorithmica.org/tg/shortest-paths Кратчайшие пути в графе], [https://ru.algorithmica.org/cs/shortest-paths/dijkstra/ Алгоритм Дейкстры]
* [https://algs4.cs.princeton.edu/lectures/keynote/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures — 4.4 Shortest Paths]
* [https://brilliant.org/wiki/dijkstras-short-path-finder brilliant.org — Dijkstra's Shortest Path Algorithm]
* [https://usaco.guide/gold/shortest-paths?lang=cpp#dijkstra usaco.guide — Dijkstra]
Демонстрация:
* [https://visualgo.net/en/sssp visualgo.net — Single-Source Shortest Paths]
* [https://www.cs.usfca.edu/~galles/visualization/Dijkstra.html www.cs.usfca.edu/~galles — Dijkstra Shortest Path]
Код:
* [https://github.com/indy256/codelibrary/blob/master/cpp/graphs/shortestpaths/dijkstra.cpp indy256/codelibrary/cpp/graphs/shortestpaths/dijkstra.cpp]
* [https://github.com/ADJA/algos/blob/master/Graphs/DijkstraSet.cpp ADJA/algos/Graphs/DijkstraSet.cpp]
* [https://github.com/kevin-wayne/algs4/blob/master/src/main/java/edu/princeton/cs/algs4/DijkstraSP.java kevin-wayne/algs4/DijkstraSP.java]
Задачи:
* [https://informatics.msk.ru/course/view.php?id=6#section-4 informatics.msk.ru — Курс «Алгоритмы на графах», тема «Алгоритм Дейкстры»]
* [http://acmp.ru/?main=task&id_task=132 ACMP #132 Алгоритм Дейкстры]
* [http://acmp.ru/?main=task&id_task=133 ACMP #133 Заправки]
* [http://acmp.ru/?main=task&id_task=134 ACMP #134 — Автобусы]
* [http://acmp.ru/?main=task&id_task=260 ACMP #260 — Олимпиада по алхимии]
* [http://acmp.ru/?main=task&id_task=469 ACMP #469 Химическая тревога]
* [http://codeforces.ru/gym/100070/problem/L Codeforces #100070.L — Островные государства]


[[Category:Кратчайшие пути из одной вершины]]
[[Category:Кратчайшие пути из одной вершины]]

Текущая версия от 15:26, 24 мая 2023

TLDR

Общие сведения

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

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

Итак, пусть v — текущая ближайшая вершина и существует ребро v → to веса w. Обозначим кратчайшее расстояние до вершины v как dist[v], текущее расстояние до вершины to — dist[to]. Тогда если (dist[v] + w) < dist[to], то мы нашли более короткий путь к вершине to — он проходит через вершину v и ребро v → to. Следовательно, мы можем обновить значение dist[to]. Такое обновление называется релаксацией.

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

Доказательство корректности алгоритма Дейкстры

Доказательство того факта, что на каждой итерации расстояние до обрабатываемой вершины действительно является кратчайшим, проводится по индукции. Для базового случая (обрабатывается стартовая вершина, расстояние до неё равно нулю) утверждение выполняется. Далее, пусть утверждение выполняется для всех обработанных вершин (значения dist[] для них рассчитаны верно), а на текущем шаге выбрана вершина v. Обозначим через u первую необработанную вершину на кратчайшем пути до v, через t — вершину, предшествующую u на этом пути. Кратчайшее расстояние до вершины u равно сумме dist[t] и веса ребра t → u; эта сумма уже была записана в dist[u] при проведении релаксаций из вершины t, следовательно, значение dist[u] действительно равно кратчайшему расстоянию до вершины u. Далее, заметим, что должны выполняться условия dist[v] ≤ dist[u] (так как вершина v является ближайшей на текущем шаге) и dist[v] ≥ dist[u] (так как u лежит на пути до v, а граф не содержит рёбер отрицательного веса). Отсюда dist[v] = dist[u], то есть в момент выбора вершины v значение dist[v] действительно равно кратчайшему расстоянию до неё.

Демонстрация работы

Реализация для плотных графов

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

struct Edge {
    int to, weight;
};

vector<vector<Edge>> graph(vertexCount);

Алгоритм принимает индекс стартовой вершины start и заполняет массив dist. Роль значения «бесконечность» выполняет достаточно большая константа INF; её значение должно быть больше максимального возможного расстояния между вершинами, но не допускать переполнения при проведении релаксаций (для избежания переполнений также можно ввести в основной цикл контрольное условие: если расстояние до ближайшей вершины равно INF, выполнение алгоритма завершается). Логический массив visited предназначен для отметки обработанных вершин.

После начальной инициализации visited и dist производится vertexCount итераций алгоритма, на каждой из которых сначала определяется ближайшая из необработанных вершин (используется наивный поиск минимума с асимптотикой O(V)), затем выбранная вершина помечается как обработанная и производится попытка релаксации для каждого исходящего из неё ребра.

Хотя на каждой итерации выполняется различное число попыток релаксации, общее их количество равно E, так как будет просмотрено каждое ребро (один раз, если рёбра направленные, дважды — если ненаправленные). Таким образом, общая асимптотическая оценка алгоритма равна O(V2 + E).

const int INF = 1e9;

vector<int> dijkstra(vector<vector<Edge>> &graph, int start) {
    vector<bool> visited(graph.size());
    vector<int> dist(graph.size(), INF);
    dist[start] = 0;

    for (int i = 0; i < graph.size(); i++) {
        int nearestV = -1;
        for (int v = 0; v < graph.size(); v++)
            if (!visited[v] && (nearestV == -1 || dist[v] < dist[nearestV]))
                nearestV = v;

        visited[nearestV] = true;

        for (auto &[to, weight] : graph[nearestV])
            if (dist[to] > dist[nearestV] + weight)
                dist[to] = dist[nearestV] + weight;
    }

    return dist;
}

Реализация для разреженных графов

Алгоритм Дейкстры выполняет O(V) поисков ближайшей вершины и O(E) релаксаций. В предыдущей реализации информация о расстоянии до вершин хранилась в массиве, что позволяло производить операции первого типа за O(V), второго типа — за O(1). Итоговая оценка O(V2 + E) является неудовлетворительной для разреженных графов (в которых E << V2). Поэтому в данном случае имеет смысл использовать структуры данных, позволяющие производить и поиск минимума, и обновление элементов с асимптотикой O(logV).

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

Теперь для определения ближайшей вершины достаточно обратиться к полю unvisited.begin(). При проведении релаксации нужно предварительно удалить из множества пару со старым расстоянием (если она там была), а затем добавить пару с обновлённым расстоянием.

Итоговая асимптотика данной реализации составляет O((V + E)logV), что в большинстве случаев сводится к O(ElogV). Следует обратить внимание на то, что для плотных графов (в которых E ≈ V2) эта реализация оказывается медленнее предыдущей.

const int INF = 1e9;

vector<int> dijkstra(vector<vector<Edge>> &graph, int start) {
    vector<int> dist(graph.size(), INF);
    set<pair<int, int>> unvisited;
    dist[start] = 0;
    unvisited.insert({ dist[start], start });

    while (!unvisited.empty()) {
        int nearestV = unvisited.begin()->second;
        unvisited.erase(unvisited.begin());

        for (auto &[to, weight] : graph[nearestV]) {
            if (dist[to] > dist[nearestV] + weight) {
                unvisited.erase({ dist[to], to });
                dist[to] = dist[nearestV] + weight;
                unvisited.insert({ dist[to], to });
            }
        }
    }

    return dist;
}

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

Если в задаче требуется выводить сами кратчайшие пути, то нужно поддерживать массив предков from: ячейка from[v] содержит индекс непосредственного предка вершины v на кратчайшем пути от стартовой вершины до v. Изначально предок каждой вершины не определён, что помечается значением -1; обновление предка происходит вместе с обновлением кратчайшего расстояния при успешной релаксации.

После завершения работы алгоритма можно восстановить кратчайший путь от начальной вершины до некоторой достижимой вершины finish в обратном порядке, последовательно перемещаясь по массиву from, пока текущая вершина не станет равной -1. В конце нужно развернуть получившуюся последовательность вершин.

vector<int> from(n, -1);

if (dist[to] > dist[nearestV] + weight) {             
    dist[to] = dist[nearestV] + weight;
    from[to] = nearestV;          
}
 
vector<int> path;

for (int v = finish; v != -1; v = from[v])
    path.push_back(v);

reverse(path.begin(), path.end());

Если в графе присутствуют кратные рёбра между одной и той же парой вершин, то логику определения кратчайшего пути придётся усложнить. В данных условиях можно явно сохранить все рёбра графа в отдельном массиве, а в массив parent записывать индекс того ребра, по которому осуществлялась релаксация. При этом можно изменить представление графа: вместо хранения списка смежных рёбер для каждой вершины (vector<vector<Edge>> graph) можно хранить список индексов этих рёбер в массиве рёбер (vector<vector<int>> graph).

Ссылки

Теория:

Демонстрация:

Код:

Задачи: