← Назад к графовым алгоритмам

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

Поиск кратчайших расстояний от стартовой вершины (O(m log n) с кучей)

🐍 Python
import heapq

n, m, s, t = map(int, input().split())
INF = 10**10
G = [[] for _ in range(n)]

for _ in range(m):
    a, b, w = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append((b, w))
    G[b].append((a, w))

D = [INF] * n
D[s] = 0
Q = []
heapq.heappush(Q, (0, s))

while Q:
    d, i = heapq.heappop(Q)
    if d > D[i]:
        continue
    for j, w in G[i]:
        if D[i] + w < D[j]:
            D[j] = D[i] + w
            heapq.heappush(Q, (D[j], j))

if D[t] >= INF:
    print(-1)
else:
    print(D[t])
⚙️ C++
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
typedef long long ll;
const ll INF = 1e18;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int n, m;
    cin >> n >> m;

    vector<vector<pair<ll, ll>>> G(n);
    for (int i = 0; i < m; ++i) {
        int a, b;
        ll w;
        cin >> a >> b >> w;
        a--;
        b--;
        G[a].emplace_back(b, w);
        G[b].emplace_back(a, w);
    }
    
    vector<ll> D(n, INF);
    D[0] = 0;
    priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>> Q;
    Q.emplace(0, 0);

    while (!Q.empty()) {
        auto [d, i] = Q.top();
        Q.pop();
        if (d > D[i]) continue;
        for (auto [j, w] : G[i]) {
            if (D[i] + w < D[j]) {
                D[j] = D[i] + w;
                Q.emplace(D[j], j);
            }
        }
    }

    for (int i = 0; i < n; ++i) {
        cout << D[i] << " ";
    }

    return 0;
}

Как работает алгоритм Дейкстры?

Алгоритм Дейкстры находит кратчайшие пути от стартовой вершины до всех остальных в графе с неотрицательными весами.

Сравнение реализаций: Существует также реализация Дейкстры за O(n²), которая использует наивный поиск минимальной вершины и эффективна для плотных графов. Текущая реализация с кучей работает быстрее на разреженных графах.

Принцип работы

  1. Назначаем стартовой вершине расстояние 0, всем остальным — бесконечность.
  2. На каждом шаге выбираем вершину с наименьшим текущим расстоянием среди ещё не обработанных.
  3. Для выбранной вершины смотрим на всех её соседей. Если путь через текущую вершину к соседу короче, чем уже известное расстояние до соседа, то обновляем это расстояние.
  4. Помечаем текущую вершину как обработанную и больше к ней не возвращаемся.
  5. Повторяем шаги 2-4, пока все вершины не будут обработаны.

Ключевая идея

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

Оптимизация с кучей

Вместо линейного поиска минимальной вершины (как в версии за O(n²)), используется двоичная куча (priority queue). Это позволяет быстро извлекать вершину с минимальным расстоянием и добавлять обновлённые расстояния.

Временная сложность: O(m log n), где n — количество вершин, m — количество рёбер.

Пространственная сложность: O(n + m)

Пример работы

Рассмотрим граф из 4 вершин и 5 рёбер:

Рёбра (a, b, w):
0-1: 5
0-2: 3
1-2: 2
1-3: 7
2-3: 4

Стартовая вершина: s = 0

Шаги алгоритма:

Инициализация: D = [0, ∞, ∞, ∞]
Куча: (0, 0)

Шаг 1: извлекаем (0, 0) → обрабатываем вершину 0
       обновляем: D[1] = 5, D[2] = 3
       куча: (3, 2), (5, 1)

Шаг 2: извлекаем (3, 2) → обрабатываем вершину 2
       обновляем: D[1] = min(5, 3+2=5) = 5, D[3] = 3+4=7
       куча: (5, 1), (7, 3)

Шаг 3: извлекаем (5, 1) → обрабатываем вершину 1
       обновляем: D[3] = min(7, 5+7=12) = 7
       куча: (7, 3)

Шаг 4: извлекаем (7, 3) → обрабатываем вершину 3
       нет улучшений

Результат: D = [0, 5, 3, 7]

Кратчайшие расстояния от вершины 0:
до 1: 5, до 2: 3, до 3: 7

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

Введите рёбра графа и найдите кратчайшее расстояние:

Результат появится здесь...