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

Алгоритм поиска кратчайших путей от одной вершины до всех остальных в графе с неотрицательными весами рёбер.

Идея алгоритма простыми словами

Мы представляем граф как сеть дорог, где веса рёбер — это длина или стоимость пути. Алгоритм Дейкстры постепенно «расширяет» зону вершин, для которых уже известно лучшее расстояние от старта. На каждом шаге мы выбираем вершину с минимальной текущей оценкой расстояния и пытаемся улучшить пути к её соседям.

Асимптотика (классическая реализация):

С приоритетной очередью (кучей): O((V + E) log V)
Память: O(V) для хранения расстояний и очереди

Плюсы

Находит оптимальные кратчайшие пути при неотрицательных весах;
Подходит для многих реальных задач (навигаторы, сети);
Хорошо комбинируется с кучей (heap) и другими структурами.

Минусы

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

Пример кода

// adj: объект { v: [ { to, weight }, ... ] }
function dijkstra(adj, start) {
  const dist = {};
  const visited = new Set();

  for (const v in adj) {
    dist[v] = Infinity;
  }
  dist[start] = 0;

  while (true) {
    let vMin = null;
    let best = Infinity;

    for (const v in dist) {
      if (!visited.has(v) && dist[v] < best) {
        best = dist[v];
        vMin = v;
      }
    }

    if (vMin === null) break;
    visited.add(vMin);

    for (const edge of adj[vMin] ?? []) {
      const to = edge.to;
      const w = edge.weight;
      if (dist[vMin] + w < dist[to]) {
        dist[to] = dist[vMin] + w;
      }
    }
  }

  return dist;
}

Попробуй самостоятельно написать алгоритм, а затем сравнить

НазадBFS и DFS ВпередОчередь и стек - Общая информация

Полезные темы

Рекомендуем изучить эти темы для лучшего понимания