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

Алгоритм Дейкстры (Dijkstra's algorithm) — жадный алгоритм нахождения кратчайших путей от одной исходной вершины до всех остальных в взвешенном графе с неотрицательными весами рёбер.

Зачем нужно

Поиск кратчайшего пути — одна из самых распространённых задач в программировании: навигация, сети, игровые карты, маршрутизация пакетов. Алгоритм Дейкстры даёт оптимальное решение за O((V + E) log V) при использовании приоритетной очереди, что применимо к графам с миллионами вершин.

Где используется

  • GPS-навигация (кратчайший маршрут)
  • Сетевая маршрутизация (протокол OSPF)
  • Игровые движки (pathfinding на картах)
  • Авиационное расписание (минимальное время перелёта с пересадками)
  • Социальные графы (степень близости между пользователями)

Основной контент

Идея алгоритма

  1. Установить расстояние до исходной вершины = 0, до остальных = ∞.
  2. Поместить исходную вершину в min-heap по расстоянию.
  3. Извлечь вершину с минимальным расстоянием.
  4. Для каждого соседа: если dist[u] + weight(u,v) < dist[v] — обновить и добавить в heap.
  5. Повторять до пустой очереди.
function dijkstra(graph, start) {
  // graph: Map<node, Array<{node, weight}>>
  const dist = new Map();
  for (const node of graph.keys()) dist.set(node, Infinity);
  dist.set(start, 0);

  // MinHeap через массив (упрощённо)
  const heap = [[0, start]]; // [distance, node]

  while (heap.length > 0) {
    heap.sort((a, b) => a[0] - b[0]); // в реальном CP используют PriorityQueue
    const [d, u] = heap.shift();

    if (d > dist.get(u)) continue; // устаревшая запись

    for (const { node: v, weight } of (graph.get(u) || )) {
      const newDist = dist.get(u) + weight;
      if (newDist < dist.get(v)) {
        dist.set(v, newDist);
        heap.push([newDist, v]);
      }
    }
  }
  return dist;
}

// Пример графа
const graph = new Map([
  ['A', [{ node: 'B', weight: 4 }, { node: 'C', weight: 2 }]],
  ['B', [{ node: 'D', weight: 3 }, { node: 'C', weight: 1 }]],
  ['C', [{ node: 'B', weight: 1 }, { node: 'D', weight: 5 }]],
  ['D', ],
]);

const distances = dijkstra(graph, 'A');
// A→0, B→3 (A→C→B), C→2, D→6 (A→C→B→D)
console.log(distances.get('D')); // 6

Восстановление пути

// Добавить Map prev: при обновлении dist[v] записывать prev.set(v, u)
// Путь: идти от target по prev до start в обратном порядке
function getPath(prev, start, target) {
  const path = ;
  let cur = target;
  while (cur !== start) {
    path.unshift(cur);
    cur = prev.get(cur);
    if (cur === undefined) return null; // путь не существует
  }
  path.unshift(start);
  return path;
}

Сложность

Реализация Время Память
Массив (наивная) O(V^2) O(V)
Binary heap + adj.list O((V + E) log V) O(V + E)
Fibonacci heap O(V log V + E) O(V + E)

Частые ошибки

  • Применять алгоритм к графу с отрицательными рёбрами — даёт неверный результат; для этого нужен алгоритм Беллмана–Форда.
  • Не пропускать устаревшие записи в heap (if d > dist[u] continue) — ведёт к лишним итерациям или ошибкам.
  • Использовать сортировку массива вместо настоящей min-heap — сложность деградирует до O(E·V).
  • Путать алгоритм Дейкстры с BFS: BFS работает только для невзвешенных графов.

Связанные темы

Ресурсы