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

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


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


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


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


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


vector<bool> visited(n);
vector<int> dist(n);
  const int INF = 1e9;
  const int INF = 1e9;
   
   
  void dijkstra(int vStart) {
  vector<int> dijkstra(vector<vector<Edge>> &graph, int start) {
     fill(visited.begin(), visited.end(), 0);
     vector<bool> visited(graph.size());
     fill(dist.begin(), dist.end(), INF);
     vector<int> dist(graph.size(), INF);
     dist[vStart] = 0;
     dist[start] = 0;
   
     for (int i = 0; i < n; i++) {
     for (int i = 0; i < graph.size(); i++) {
         int nearestV = -1;
         int nearestV = -1;
         for (int v = 0; v < n; v++)
         for (int v = 0; v < graph.size(); v++)
             if (!visited[v] && (nearestV == -1 || dist[v] < dist[nearestV]))
             if (!visited[v] && (nearestV == -1 || dist[v] < dist[nearestV]))
                 nearestV = v;
                 nearestV = v;
Строка 48: Строка 50:
         visited[nearestV] = true;
         visited[nearestV] = true;
   
   
         for (Edge &e : g[nearestV]) {
         for (auto &[to, weight] : graph[nearestV])
            int to = e.to, w = e.weight;
             if (dist[to] > dist[nearestV] + weight)
             if (dist[to] > dist[nearestV] + w)
                 dist[to] = dist[nearestV] + weight;
                 dist[to] = dist[nearestV] + w;
        }             
     }
     }
    return dist;
  }
  }


Строка 60: Строка 62:
Алгоритм Дейкстры выполняет O(V) поисков ближайшей вершины и O(E) релаксаций. В предыдущей реализации информация о расстоянии до вершин хранилась в массиве, что позволяло производить операции первого типа за O(V), второго типа — за 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>) эта реализация оказывается медленнее предыдущей.


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


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


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


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


{| width="100%"
{| width="100%"
| width="50%"  |
| width="50%"  |
  vector<int> parent(n, -1);
  vector<int> from(n, -1);
   
   
  if (dist[to] > dist[nearestV] + w) {             
  if (dist[to] > dist[nearestV] + weight) {             
     dist[to] = dist[nearestV] + w;
     dist[to] = dist[nearestV] + weight;
     parent[to] = nearestV;           
     from[to] = nearestV;           
  }
  }
| width="10px" | &nbsp;
| width="10px" | &nbsp;
Строка 108: Строка 110:
  vector<int> path;
  vector<int> path;
   
   
  for (int v = vFinish; v != -1; v = parent[v])
  for (int v = finish; v != -1; v = from[v])
      path.push_back(v);
    path.push_back(v);
 
  reverse(path.begin(), path.end());
  reverse(path.begin(), path.end());
|}
|}


Если в графе присутствуют кратные рёбра между одной и той же парой вершин, то логику определения кратчайшего пути придётся усложнить. В данных условиях можно явно сохранить все рёбра графа в отдельном массиве, а в массив <tt>parent[]</tt> записывать индекс того ребра, по которому осуществлялась релаксация. При этом можно изменить представление графа: вместо хранения списка смежных рёбер для каждой вершины (<tt>vector<vector<Edge>> g</tt>) можно хранить список индексов этих рёбер в массиве рёбер (<tt>vector<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; Автобусы]
* [http://acmp.ru/?main=task&id_task=260 ACMP #260 &mdash; Олимпиада по алхимии]
* [http://acmp.ru/?main=task&id_task=469 ACMP #469 &mdash; Химическая тревога]
* [http://codeforces.ru/gym/100070/problem/L Codeforces #100070.L &mdash; Островные государства]


== Ссылки ==
== Ссылки ==
* [http://e-maxx.ru/algo/dijkstra e-maxx.ru &mdash; Алгоритм Дейкстры за O(N<sup>2</sup> + M)]
Теория:
* [http://e-maxx.ru/algo/dijkstra_sparse e-maxx.ru &mdash; Алгоритм Дейкстры за O(MlogN)]
* 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://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 &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]
* [http://brestprog.by/topics/dijkstra/ brestprog — Взвешенные графы. Алгоритм Дейкстры]
* [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 Алгоритм Дейкстры]
* [http://algorithmica.org/tg/shortest-paths algorithmica.org — Кратчайшие пути в графе]
* [https://brestprog.by/topics/dijkstra/ brestprog.by — Взвешенные графы. Алгоритм Дейкстры]
* [http://informatics.mccme.ru/course/view.php?id=6 informatics.mccme.ru &mdash; Курс &laquo;Алгоритмы на графах&raquo; &mdash; часть 4]
* algorithmica.org — [http://algorithmica.org/tg/shortest-paths Кратчайшие пути в графе], [https://ru.algorithmica.org/cs/shortest-paths/dijkstra/ Алгоритм Дейкстры]
* [http://algs4.cs.princeton.edu/lectures/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures &mdash; 4.4 Shortest Paths]
* [https://algs4.cs.princeton.edu/lectures/keynote/44ShortestPaths.pdf algs4.cs.princeton.edu/lectures 4.4 Shortest Paths]
* [http://brilliant.org/wiki/dijkstras-short-path-finder Brilliant.org — Dijkstra's Shortest Path Algorithm]
* [https://brilliant.org/wiki/dijkstras-short-path-finder brilliant.org — Dijkstra's Shortest Path Algorithm]
* [http://visualgo.net/sssp.html VisuAlgo &mdash; Single-Source Shortest Paths]
* [https://usaco.guide/gold/shortest-paths?lang=cpp#dijkstra usaco.guide — Dijkstra]
* [http://github.com/indy256/codelibrary/blob/master/java/src/Dijkstra.java CodeLibrary &mdash; Dijkstra's algorithm in O(V^2)]
Демонстрация:
* [http://github.com/indy256/codelibrary/blob/master/java/src/DijkstraHeap.java CodeLibrary &mdash; Dijkstra's algorithm in O(ElogV)]
* [https://visualgo.net/en/sssp visualgo.net — Single-Source Shortest Paths]
* [http://github.com/ADJA/algos/blob/master/Graphs/DijkstraSet.cpp Algos &mdash; Dijkstra on set for sparse graphs]
* [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).

Ссылки

Теория:

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

Код:

Задачи: