Дейкстра: следим за каждой строкой

Граф и расстояния

Под вершиной — dist. Оранжевое ребро сейчас проверяется; зелёный маршрут появится после завершения. «Подтверждено» — пояснение на рисунке, отдельного массива visited в коде нет.

Очередь с приоритетом q

Каждая карточка — пара (расстояние, вершина). Первая обведена оранжевым.

Показан порядок извлечения, а не внутренний массив кучи. Серые записи устарели: они останутся в очереди до извлечения и проверки.

Таблица путей

Во время работы ∞ означает «ещё не найдено», после завершения — «недостижимо». parent = −1 показан прочерком.

Код C++17

Подсветка показывает только что выполненную строку. Таблица и переменные — состояние после этого шага. Закрывающие скобки C++ обозначают выход из области видимости.

1. dist[s] = 0;
2. q.push({0, s});
3. while (!q.empty()) {
4. auto [du, v] = q.top();
5. q.pop();
6. if (du != dist[v]) {
7. continue;
8. }
9. for (auto [u, w] : adj[v]) {
10. long long nd = du + w;
11. if (nd < dist[u]) {
12. dist[u] = nd;
13. parent[u] = v;
14. q.push({nd, u});
15. }
16. }
17. }

1. dist[s] = 0
2. heappush(q, (0, s))
3. while q:
4. du, v = heappop(q)
5. if du != dist[v]:
6. continue
7. for u, w in adj[v]:
8. nd = du + w
9. if nd < dist[u]:
10. dist[u] = nd
11. parent[u] = v
12. heappush(q, (nd, u))

Переменные

s

—

du

—

v

—

u

—

w

—

nd

—

s — старт; v — извлечённая вершина; du — расстояние в записи; u — сосед; w — вес; nd — новая стоимость. Прочерк означает «ещё не задана» или «вне области видимости».

#include <iostream>
#include <vector>
#include <queue>
#include <functional>
#include <utility>
#include <algorithm>
using namespace std;

// n — число вершин, s — старт (номера от 1 до n).
// adj[v] содержит пары {сосед, вес}.
const long long INF = 1LL << 62;
vector<long long> dist(n + 1, INF);
vector<int> parent(n + 1, -1);
using State = pair<long long, int>;
priority_queue<State, vector<State>, greater<State>> q;

from heapq import heappush, heappop

# n — число вершин, s — старт (номера от 1 до n).
# adj[v] содержит пары (сосед, вес).
INF = float("inf")
dist = [INF] * (n + 1)
parent = [-1] * (n + 1)
q = []