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

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

Дайте каждой вершине расстояние бесконечность. Стартовая получает ноль.

Положите старт в кучу с ключом по расстоянию. Куча всегда отдаёт ближайшую вершину.

Снимите вершину с кучи. Если сохранённое расстояние лучше снятого, пропустите её.

Иначе вершина закрыта. Её расстояние окончательно и больше не улучшится.

Для каждого исходящего ребра сравните сохранённое расстояние с маршрутом через эту вершину. Если новый короче, запишите его и положите в кучу.

Повторяйте, пока куча не опустеет. Каждая достижимая вершина закрыта один раз.

Источники: Википедия: Алгоритм Дейкстры, Dijkstra (1959), A note on two problems in connexion with graphs (англ.)

1. расстояния: A 0, B inf, C infТри ребра: A в B за 1, A в C за 4. Из B в C за 2.
2. снимаем A и ослабляемB становится 1, а C становится 4.
3. снимаем B с 1, ослабляем CНоль плюс 1 плюс 2 это 3, и это лучше 4.
4. расстояния: A 0, B 1, C 3C кладётся в кучу заново с лучшим значением.
5. снимаем C с 3, потом C с 4Устаревшая запись пропускается, тройка уже лучше.

function dijkstra(n, adj, source) {
    const dist = new Array(n).fill(Infinity);
    dist[source] = 0;
    const heap = [[0, source]]; // [distance, node]
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]); // swap for a real heap in production
        const [d, u] = heap.shift();
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u] || []) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.push([dist[v], v]);
            }
        }
    }
    return dist;
}

function dijkstra(n: number, adj: Array<Array<[number, number]>>, source: number): number[] {
    const dist = new Array<number>(n).fill(Infinity);
    dist[source] = 0;
    const heap: Array<[number, number]> = [[0, source]]; // [distance, node]
    while (heap.length) {
        heap.sort((a, b) => a[0] - b[0]); // swap for a real heap in production
        const [d, u] = heap.shift()!;
        if (d > dist[u]) continue;
        for (const [v, w] of adj[u] ?? []) {
            if (d + w < dist[v]) {
                dist[v] = d + w;
                heap.push([dist[v], v]);
            }
        }
    }
    return dist;
}

import heapq

def dijkstra(n, adj, source):
    dist = [float('inf')] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        d, u = heapq.heappop(heap)
        if d > dist[u]:
            continue
        for v, w in adj.get(u, []):
            if d + w < dist[v]:
                dist[v] = d + w
                heapq.heappush(heap, (dist[v], v))
    return dist

function dijkstra(int $n, array $adj, int $source): array {
    $dist = array_fill(0, $n, INF);
    $dist[$source] = 0;
    $heap = new SplPriorityQueue();
    $heap->insert($source, 0);
    while (!$heap->isEmpty()) {
        $u = $heap->extract();
        foreach ($adj[$u] ?? [] as [$v, $w]) {
            if ($dist[$u] + $w < $dist[$v]) {
                $dist[$v] = $dist[$u] + $w;
                $heap->insert($v, -$dist[$v]); // max-heap: negate for min-order
            }
        }
    }
    return $dist;
}

    public static int[] dijkstra(int n, List<List<int[]>> adj, int source) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;
        // {distance, node}, smallest distance first
        PriorityQueue<int[]> heap = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
        heap.add(new int[] { 0, source });
        while (!heap.isEmpty()) {
            int[] top = heap.poll();
            int d = top[0], u = top[1];
            if (d > dist[u]) continue;
            for (int[] edge : adj.get(u)) {
                int v = edge[0], w = edge[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    heap.add(new int[] { dist[v], v });
                }
            }
        }
        return dist;
    }

    public static int[] Dijkstra(int n, List<List<int[]>> adj, int source) {
        var dist = new int[n];
        Array.Fill(dist, int.MaxValue);
        dist[source] = 0;
        // the node, keyed by its distance: smallest first
        var heap = new PriorityQueue<int, int>();
        heap.Enqueue(source, 0);
        while (heap.Count > 0) {
            heap.TryDequeue(out int u, out int d);
            if (d > dist[u]) continue;
            foreach (var edge in adj[u]) {
                int v = edge[0], w = edge[1];
                if (d + w < dist[v]) {
                    dist[v] = d + w;
                    heap.Enqueue(v, dist[v]);
                }
            }
        }
        return dist;
    }

Алгоритм Дейкстры: разбор примера

За сколько сигнал дойдёт до всех

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

Если какая-то вершина недостижима, верните минус один.

Задача о сигнале это один запуск кратчайших путей из одного источника.

Ответ это наибольшее из итоговых расстояний. Недостижимая вершина оставит бесконечность.

function networkDelayTime(times, n, k) {
    const graph = new Map();
    for (const [from, to, weight] of times) {
        if (!graph.has(from)) graph.set(from, []);
        graph.get(from).push([to, weight]);
    }

    const dist = new Map([[k, 0]]);
    const heap = new MinHeap((entry) => entry[0]); // entries are [distance, node]
    heap.push([0, k]);

    while (heap.size()) {
        const [d, node] = heap.pop();
        if (d > (dist.get(node) ?? Infinity)) continue; // a stale entry

        for (const [next, weight] of graph.get(node) ?? []) {
            const candidate = d + weight;
            if (candidate < (dist.get(next) ?? Infinity)) {
                dist.set(next, candidate);
                heap.push([candidate, next]);
            }
        }
    }

    if (dist.size < n) return -1;
    return Math.max(...dist.values());
}

Алгоритм Дейкстры: когда применять?

Паттерн «Алгоритм Дейкстры» нужен, когда в условии есть слова «самый дешёвый/короткий путь со взвешенными рёбрами», «неотрицательные веса рёбер» или «минимальная суммарная стоимость до каждого узла». Решение на нём обычно укладывается в O(E log V).

• •самый дешёвый/короткий путь со взвешенными рёбрами
• •неотрицательные веса рёбер
• •минимальная суммарная стоимость до каждого узла
• •задержка в сети / стоимость маршрута, а не число дорог
• •взвешенный граф, кратчайшие пути из одного источника

Слова в условии для всех паттернов собраны в одной таблице: шпаргалка по паттернам алгоритмов.

Алгоритм Дейкстры: с чем путают?

Паттерн «Алгоритм Дейкстры» чаще всего путают с этими паттернами: Обход графа BFS / DFS, Бинарная куча / очередь с приоритетом, Жадный алгоритм (обменный аргумент) и Топологическая сортировка (алгоритм Кана).

• Обход графа BFS / DFS (Graph BFS / DFS): Очередь считает шаги и считает все рёбра одинаковыми. Куча умеет работать с настоящими весами.
• Бинарная куча / очередь с приоритетом (Binary heap / priority queue): Куча это инструмент, на котором всё держится. Та страница про сам контейнер.
• Жадный алгоритм (обменный аргумент) (Greedy (exchange argument)): Закрывать ближайшую вершину это жадный выбор. Он верен, пока нет отрицательных весов.
• Топологическая сортировка (алгоритм Кана) (Topological sort (Kahn's algorithm)): В графе без циклов порядок ослабляет рёбра без всякой кучи. Так быстрее, и отрицательные веса допустимы.

Алгоритм Дейкстры: частые ошибки

• Запускают на отрицательных весах

  Закрытая вершина всё ещё может улучшиться, и жадный шаг рушится. Там нужен Беллман-Форд.

• Не пропускают устаревшие записи кучи

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

• Закрывают вершину при вставке

  Рано положенная вершина позже может получить путь лучше. Закрывайте при снятии, а не при вставке.

• Берут обычную очередь

  Очередь считает рёбра, а не вес. Это совпадает, только если все рёбра стоят одинаково.

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

Паттерн «Алгоритм Дейкстры» решает такие задачи с собеседований: Время задержки в сети, Дешёвый перелёт с k пересадками, Путь с наименьшим усилием, Плавание в поднимающейся воде, Путь с наибольшей вероятностью, Минимальная стоимость до последней клетки и Второй кратчайший путь.

• Время задержки в сети: Чистая форма: ответ это наибольшее расстояние.
• Дешёвый перелёт с k пересадками: Лимит пересадок добавляет к состоянию второе измерение.
• Путь с наименьшим усилием: Стоимость пути это его худший шаг.
• Плавание в поднимающейся воде: То же самое, но с максимумом вместо суммы.
• Путь с наибольшей вероятностью: Здесь умножают, а не складывают, и берут наибольшее.
• Минимальная стоимость до последней клетки: Сетка это граф с четырьмя рёбрами на клетку.
• Второй кратчайший путь: Храните два лучших расстояния на вершину.

Алгоритм Дейкстры: сложность по времени и памяти

У паттерна «Алгоритм Дейкстры» целевая сложность O(E log V).

V вершин и E рёбер дают O(E log V) с кучей. Отрицательные веса её ломают, там нужен Беллман-Форд.