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

1. Кратчайший — значит с минимальной суммой весов

Представь карту дорог. Вершины — города, рёбра — дороги, а вес ребра — время или цена поездки. Стоимость маршрута — сумма весов всех его рёбер.

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

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

1. Положи dist[s] = 0 и добавь в очередь пару (0, s).
2. Извлеки минимальную пару (du, v). Здесь du — расстояние, записанное в этой паре.
3. Если du != dist[v], запись устарела. Пропусти её и извлеки следующую.
4. Для каждого ребра v → u веса w вычисли nd = du + w. Если nd < dist[u], обнови dist[u], запиши parent[u] = v и добавь новую пару (nd, u).
5. Повторяй, пока очередь не опустеет.

5. C++ и Python: одинаковая идея, разные команды

В списке adj[v] храним пары «сосед, вес». Для направленного ребра добавляем только a → b. Для ненаправленного — и a → b, и b → a.

#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 = []

Основная часть алгоритма

dist[s] = 0;
q.push({0, s});
while (!q.empty()) {
 auto [du, v] = q.top();
 q.pop();
 if (du != dist[v]) {
 continue;
 }
 for (auto [u, w] : adj[v]) {
 long long nd = du + w;
 if (nd < dist[u]) {
 dist[u] = nd;
 parent[u] = v;
 q.push({nd, u});
 }
 }
}

dist[s] = 0
heappush(q, (0, s))
while q:
 du, v = heappop(q)
 if du != dist[v]:
 continue
 for u, w in adj[v]:
 nd = du + w
 if nd < dist[u]:
 dist[u] = nd
 parent[u] = v
 heappush(q, (nd, u))

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

7. Готовые программы: прочитай граф и найди расстояния

Формат: n вершин, m направленных рёбер, затем m строк a b w. Старт — вершина 1. Выводим расстояния до всех вершин, для недостижимых — −1. В задаче CSES Shortest Routes I все вершины достижимы, поэтому −1 не появится.

3 4
1 2 6
1 3 2
3 2 3
1 3 4

0 5 2

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

int main() {
 ios::sync_with_stdio(false);
 cin.tie(nullptr);
 int n, m;
 cin >> n >> m;
 vector<vector<pair<int, long long>>> adj(n + 1);
 for (int i = 0; i < m; ++i) {
 int a, b;
 long long w;
 cin >> a >> b >> w;
 adj[a].push_back({b, w}); // направленное ребро
 }
 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;
 int s = 1;
 dist[s] = 0;
 q.push({0, s});
 while (!q.empty()) {
 auto [du, v] = q.top();
 q.pop();
 if (du != dist[v]) {
 continue;
 }
 for (auto [u, w] : adj[v]) {
 long long nd = du + w;
 if (nd < dist[u]) {
 dist[u] = nd;
 parent[u] = v;
 q.push({nd, u});
 }
 }
 }
 for (int v = 1; v <= n; ++v) {
 cout << (dist[v] == INF ? -1 : dist[v]);
 cout << (v == n ? '\n' : ' ');
 }
}

import sys
from heapq import heappush, heappop

input = sys.stdin.buffer.readline
n, m = map(int, input().split())
adj = [[] for _ in range(n + 1)]
for _ in range(m):
 a, b, w = map(int, input().split())
 adj[a].append((b, w)) # направленное ребро

INF = float("inf")
dist = [INF] * (n + 1)
parent = [-1] * (n + 1)
q = []
s = 1
dist[s] = 0
heappush(q, (0, s))
while q:
 du, v = heappop(q)
 if du != dist[v]:
 continue
 for u, w in adj[v]:
 nd = du + w
 if nd < dist[u]:
 dist[u] = nd
 parent[u] = v
 heappush(q, (nd, u))
print(*(d if d != INF else -1 for d in dist[1:]))

В C++ выбранное INF больше возможных сумм в приведённых задачах. Для других ограничений отдельно проверь, что INF больше любого ответа и сложение не переполняет long long.

9. Что чаще всего мешает решению

• Зафиксировать вершину при первом обнаружении. Первый найденный путь может оказаться длиннее следующего. Окончательное расстояние получаем при извлечении актуального минимума.
• Забыть старые записи. Проверка du != dist[v] пропускает записи, для которых расстояние уже улучшилось.
• Сравнивать только вес ребра. Нужна вся стоимость: du + w.
• Перепутать направление. Авиарейс a → b не означает, что существует рейс b → a.
• Хранить большие расстояния в int. В C++ используй long long для весов и сумм.