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

Кратчайшие пути во взвешенном графе: фиксируем ближайший узел и «расслабляем» его рёбра.

время O((V + E) log V)память O(V)уровень: средний

Что происходит сейчас0/0

Нажмите Play, чтобы запустить сценарий

TypeScript — активная строка подсвечена шагом

1function dijkstra(edges: Edge[], start: string): Map<string, number> {
2  const dist = new Map<string, number>()
3  for (const v of vertices(edges)) dist.set(v, Infinity)
4  dist.set(start, 0)
5 
6  const visited = new Set<string>()
7 
8  while (visited.size < dist.size) {
9    // ближайший непосещённый узел
10    let current: string | null = null
11    for (const v of dist.keys()) {
12      if (!visited.has(v) && (current === null || (dist.get(v) ?? 0) < (dist.get(current) ?? 0))) {
13        current = v
14      }
15    }
16    visited.add(current)
17 
18    // ослабление рёбер
19    for (const e of edgesFrom(edges, current)) {
20      const candidate = (dist.get(current) ?? 0) + e.weight
21      if (candidate < (dist.get(e.to) ?? Infinity)) {
22        dist.set(e.to, candidate)
23      }
24    }
25  }
26 
27  return dist
28}

Проблема

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

Что вы видите

Сеть дорог с ценами. У каждого города — табличка d=… с текущей лучшей стоимостью добраться. Каждый шаг: берём город с минимальной табличкой (его стоимость уже окончательна), обновляем таблички соседей через его дороги.

Как это работает

Дейкстра повторяет два действия: (1) среди непосещённых выбрать вершину с минимальной дистанцией — её расстояние фиксируется навсегда, потому что любой обходной путь через более дальние вершины только длиннее; (2) «расслабить» её рёбра: если через текущую вершину до соседа дешевле, обновить его дистанцию. С приоритетной очередью — O((V+E) log V).

Пошаговый разбор

01
Инициализация
d(старт) = 0, у остальных d = ∞.
02
Выбор минимума
Ближайшая непосещённая вершина — её d окончательно.
03
Расслабление рёбер
d(сосед) = min(d(сосед), d(текущая) + вес ребра).
04
Повтор
Пока не зафиксированы все вершины.
05
Путь
Идём от цели по предкам — это кратчайший маршрут.

Complexity и ограничения

time

O((V + E) log V)

space

O(V)

Веса неотрицательные. При отрицательных рёбрах нужен Беллман–Форд.

Edge cases

Недостижимые вершины
Остаются с d = ∞ — пути нет.
Отрицательное ребро
Дейкстра ломается: «зафиксированное» расстояние может оказаться не минимальным.
Несколько равных путей
Все минимальны; алгоритм вернёт один из них.

Где встречается в реальности

Маршрутизация пакетов

Протоколы OSPF/IS-IS строят таблицы маршрутов алгоритмами семейства Дейкстры.

Карты и логистика

Оптимальный маршрут с учётом времени/стоимости участков.

IP-транзит

Выбор аплинка по суммарной стоимости линков.

Связанные алгоритмы

Поиск в ширину (BFS)Поиск в глубину (DFS)

Shorts

«Навигатор снова врёт? Почему кратчайший путь — не самый прямой»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Навигатор снова врёт? Почему кратчайший путь — не самый прямой

Нажмите Play

Бит 1/6 · 0–2 с

Hook: две дороги — какая дешевле?

script-setup.ru/algorithms/dijkstra