Как реализовать алгоритм Дейкстры на priority_queue за O(E log V)?
Понимаю идею Дейкстры (жадно берём ближайшую вершину), но не понимаю, как написать её эффективно. Видел реализацию через priority_queue в C++. Можете показать каноничный код с правильной асимптотикой и объяснить, что класть в кучу?
2 ответа
В кучу кладём пары (текущее расстояние, вершина). Берём вершину с минимальным расстоянием, релаксируем её рёбра. priority_queue в C++ — max-heap, поэтому либо храним отрицательные расстояния, либо берём greater для min-heap.
using ll = long long;
const ll INF = 1e18;
vector<vector<pair<int,int>>> g(n); // {сосед, вес}
vector<ll> dist(n, INF);
priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<>> pq;
dist[s] = 0; pq.push({0, s});
while (!pq.empty()) {
auto [d, v] = pq.top(); pq.pop();
if (d > dist[v]) continue; // устаревшая запись
for (auto [u, w] : g[v]) {
if (dist[v] + w < dist[u]) {
dist[u] = dist[v] + w;
pq.push({dist[u], u});
}
}
}
Сложность O(E log V) по времени, O(V) по памяти. Куча может содержать до E записей, каждая операция log.
Самая частая грабля — забыть строку if (d > dist[v]) continue;. Мы не удаляем устаревшие записи из кучи (стандартный priority_queue не умеет decrease-key), а просто добавляем новые. Поэтому одна вершина может лежать в куче несколько раз, и при извлечении надо проверить: если вытащенное d больше актуального dist[v] — эта запись протухла, пропускаем. Без этой проверки получите лишние релаксации (TLE), хотя ответ останется верным. Ещё: dist обязательно long long, иначе суммы весов переполнят int.