---
title: "Алгоритм Дейкстры"
url: https://algopath.pro/ru/patterns/dijkstra
language: ru
summary: "Закрывайте ближайшую незакрытую вершину и ослабляйте все её рёбра. Куча держит эту вершину всегда в одном чтении от вас."
updated: 2026-08-24
---

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

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

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

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

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

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

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

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

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

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

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

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

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

- **Обход графа BFS / DFS** - Очередь считает шаги и считает все рёбра одинаковыми. Куча умеет работать с настоящими весами.
- **Бинарная куча / очередь с приоритетом** - Куча это инструмент, на котором всё держится. Та страница про сам контейнер.
- **Жадный алгоритм (обменный аргумент)** - Закрывать ближайшую вершину это жадный выбор. Он верен, пока нет отрицательных весов.
- **Топологическая сортировка (алгоритм Кана)** - В графе без циклов порядок ослабляет рёбра без всякой кучи. Так быстрее, и отрицательные веса допустимы.

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

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

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

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

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

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

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

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

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

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

- **Запускают на отрицательных весах** Закрытая вершина всё ещё может улучшиться, и жадный шаг рушится. Там нужен Беллман-Форд.
- **Не пропускают устаревшие записи кучи** Вершину кладут несколько раз с разными расстояниями. При снятии сравнивайте с сохранённым значением.
- **Закрывают вершину при вставке** Рано положенная вершина позже может получить путь лучше. Закрывайте при снятии, а не при вставке.
- **Берут обычную очередь** Очередь считает рёбра, а не вес. Это совпадает, только если все рёбра стоят одинаково.

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

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

## JavaScript

```javascript
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;
}
```

## Python

```python
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
```

## PHP

```php
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;
}
```