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

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

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

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

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

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

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

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

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 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());
}

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

Эти формулировки в условии ведут сюда:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

O(E log V)

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