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

Почему этот алгоритм важен?

Алгоритм Дейкстры — это фундаментальный алгоритм в теории графов, который позволяет:

• 🧠 Находить кратчайшие пути от одной вершины до всех остальных в графе
• ⚡ Эффективно работать с взвешенными графами без отрицательных весов
• 🎯 Решать широкий спектр практических задач — от навигации до сетевой маршрутизации
• 🔍 Понять основы жадных алгоритмов и их применение в графовых структурах
• 🌐 Служить основой для многих других алгоритмов поиска пути

Постановка задачи

Формулировка:

Дан взвешенный граф G = (V, E), где V — множество вершин, E — множество рёбер, и каждое ребро имеет неотрицательный вес. Требуется найти кратчайшие пути от заданной начальной вершины s ∈ V до всех остальных вершин графа.

Входные данные:

• Взвешенный граф G
• Начальная вершина s

Выходные данные:

• Массив расстояний от s до каждой вершины
• (Опционально) Массив предшественников для восстановления путей

Пройди собеседование в топ-компанию

Платформа для подготовки

Решай алгоритмические задачи как профи

✓ Популярные алгоритмы✓ Разбор решений✓ AI помощь

Начать сейчас→

Пример графа:

    6
  A --- B
  |     | \
 1|    2|  3
  |     |   \
  C --- D --- E
    4       5

Пример работы:

Для начальной вершины A ожидаемый результат:

• Расстояние до A: 0
• Расстояние до B: 6
• Расстояние до C: 1
• Расстояние до D: 3 (через C)
• Расстояние до E: 8 (через C, D)

Принцип работы алгоритма

Алгоритм Дейкстры использует жадную стратегию для последовательного нахождения кратчайших путей:

1. Инициализация: Устанавливаем расстояние до начальной вершины равным 0, а до всех остальных — бесконечности.
2. Выбор вершины: На каждом шаге выбираем непосещенную вершину с наименьшим известным расстоянием.
3. Релаксация: Обновляем расстояния до соседей выбранной вершины, если через неё путь короче.
4. Повторение: Продолжаем процесс, пока не посетим все вершины или не достигнем целевой вершины.

Пошаговое объяснение с примером

Рассмотрим граф из примера выше и начальную вершину A.

Шаг 1: Инициализация

Устанавливаем:

• dist[A] = 0 (расстояние до начальной вершины)
• dist[B] = dist[C] = dist[D] = dist[E] = ∞ (расстояния до остальных вершин)
• Все вершины помечаем как непосещенные

Шаг 2: Первая итерация

• Выбираем вершину A (она имеет наименьшее расстояние — 0)
• Обновляем расстояния до соседей A:
  • dist[B] = min(∞, 0 + 6) = 6
  • dist[C] = min(∞, 0 + 1) = 1
• Отмечаем A как посещенную

Текущее состояние:

• dist[A] = 0 (посещена)
• dist[B] = 6
• dist[C] = 1
• dist[D] = dist[E] = ∞

Шаг 3: Вторая итерация

• Выбираем вершину C (она имеет наименьшее расстояние среди непосещенных — 1)
• Обновляем расстояния до соседей C:
  • dist[D] = min(∞, 1 + 4) = 5
• Отмечаем C как посещенную

Текущее состояние:

• dist[A] = 0 (посещена)
• dist[B] = 6
• dist[C] = 1 (посещена)
• dist[D] = 5
• dist[E] = ∞

Шаг 4: Третья итерация

• Выбираем вершину D (она имеет наименьшее расстояние среди непосещенных — 5)
• Обновляем расстояния до соседей D:
  • dist[B] = min(6, 5 + 2) = 6 (не изменилось)
  • dist[E] = min(∞, 5 + 5) = 10
• Отмечаем D как посещенную

Текущее состояние:

• dist[A] = 0 (посещена)
• dist[B] = 6
• dist[C] = 1 (посещена)
• dist[D] = 5 (посещена)
• dist[E] = 10

Шаг 5: Четвертая итерация

• Выбираем вершину B (она имеет наименьшее расстояние среди непосещенных — 6)
• Обновляем расстояния до соседей B:
  • dist[E] = min(10, 6 + 3) = 9
• Отмечаем B как посещенную

Текущее состояние:

• dist[A] = 0 (посещена)
• dist[B] = 6 (посещена)
• dist[C] = 1 (посещена)
• dist[D] = 5 (посещена)
• dist[E] = 9

Шаг 6: Пятая итерация

• Выбираем вершину E (последняя непосещенная вершина)
• У E нет непосещенных соседей
• Отмечаем E как посещенную

Результат:

• dist[A] = 0
• dist[B] = 6
• dist[C] = 1
• dist[D] = 5
• dist[E] = 9

Подходы к реализации

Решение 1: Базовая реализация с матрицей смежности 🔍

function dijkstra(graph, start) {
  const n = graph.length // Количество вершин

  // Инициализация массивов расстояний и посещенных вершин
  const distances = Array(n).fill(Infinity)
  const visited = Array(n).fill(false)

  // Расстояние до начальной вершины равно 0
  distances[start] = 0

  // Проходим по всем вершинам
  for (let i = 0; i < n; i++) {
    // Находим вершину с минимальным расстоянием среди непосещенных
    let minDistVertex = -1
    for (let v = 0; v < n; v++) {
      if (
        !visited[v] &&
        (minDistVertex === -1 || distances[v] < distances[minDistVertex])
      ) {
        minDistVertex = v
      }
    }

    // Если все доступные вершины посещены или недостижимы
    if (distances[minDistVertex] === Infinity) break

    // Отмечаем вершину как посещенную
    visited[minDistVertex] = true

    // Обновляем расстояния до соседей
    for (let v = 0; v < n; v++) {
      if (graph[minDistVertex][v] > 0) {
        // Если есть ребро
        const newDist = distances[minDistVertex] + graph[minDistVertex][v]
        if (newDist < distances[v]) {
          distances[v] = newDist
        }
      }
    }
  }

  return distances
}

// Пример использования
// Представление графа как матрицы смежности
const graph = [
  [0, 6, 1, 0, 0], // Ребра из вершины A
  [6, 0, 0, 2, 3], // Ребра из вершины B
  [1, 0, 0, 4, 0], // Ребра из вершины C
  [0, 2, 4, 0, 5], // Ребра из вершины D
  [0, 3, 0, 5, 0], // Ребра из вершины E
]

const startVertex = 0 // Вершина A
const distances = dijkstra(graph, startVertex)
console.log(distances) // [0, 6, 1, 5, 9]

Анализ решения:

✅ Простая и понятная реализация

✅ Не требует дополнительных структур данных

❌ Временная сложность O(V²), где V — количество вершин

❌ Неэффективен для разреженных графов

Решение 2: Оптимизация с использованием приоритетной очереди 🚀

class PriorityQueue {
  constructor() {
    this.values = []
  }

  enqueue(val, priority) {
    this.values.push({ val, priority })
    this.sort()
  }

  dequeue() {
    return this.values.shift()
  }

  sort() {
    this.values.sort((a, b) => a.priority - b.priority)
  }

  isEmpty() {
    return this.values.length === 0
  }
}

function dijkstra(graph, start) {
  const distances = {}
  const previous = {}
  const pq = new PriorityQueue()

  // Инициализация
  for (let vertex in graph) {
    if (vertex === start) {
      distances[vertex] = 0
      pq.enqueue(vertex, 0)
    } else {
      distances[vertex] = Infinity
      pq.enqueue(vertex, Infinity)
    }
    previous[vertex] = null
  }

  // Основной алгоритм
  while (!pq.isEmpty()) {
    const current = pq.dequeue().val

    // Для каждого соседа текущей вершины
    for (let neighbor in graph[current]) {
      // Вычисляем новое расстояние
      const newDistance = distances[current] + graph[current][neighbor]

      // Если нашли более короткий путь
      if (newDistance < distances[neighbor]) {
        distances[neighbor] = newDistance
        previous[neighbor] = current
        pq.enqueue(neighbor, newDistance)
      }
    }
  }

  return { distances, previous }
}

// Пример использования
// Представление графа как списка смежности
const graph = {
  A: { B: 6, C: 1 },
  B: { A: 6, D: 2, E: 3 },
  C: { A: 1, D: 4 },
  D: { B: 2, C: 4, E: 5 },
  E: { B: 3, D: 5 },
}

const { distances, previous } = dijkstra(graph, 'A')
console.log(distances) // { A: 0, B: 6, C: 1, D: 5, E: 9 }

Характеристики:

✅ Улучшенная временная сложность до O((V + E) log V) с бинарной кучей

✅ Эффективен для разреженных графов

✅ Позволяет восстанавливать пути через массив предшественников

❌ Требует реализации приоритетной очереди

❌ Простая реализация PriorityQueue выше не оптимальна (O(n) на обновление)

Решение 3: Оптимизированная реализация с бинарной кучей (min-heap) 🔧

// Реализация бинарной кучи для более эффективной приоритетной очереди
class MinHeap {
  constructor() {
    this.heap = []
    this.positions = {} // Для быстрого обновления приоритетов
  }

  insert(node, priority) {
    // Вставка нового элемента в кучу
    this.heap.push({ node, priority })
    const index = this.heap.length - 1
    this.positions[node] = index
    this.bubbleUp(index)
  }

  extractMin() {
    // Извлечение минимального элемента
    if (this.heap.length === 0) return null

    const min = this.heap[0]
    const end = this.heap.pop()
    delete this.positions[min.node]

    if (this.heap.length > 0) {
      this.heap[0] = end
      this.positions[end.node] = 0
      this.sinkDown(0)
    }

    return min
  }

  decreaseKey(node, newPriority) {
    // Уменьшение приоритета элемента
    const index = this.positions[node]
    if (index === undefined) return

    this.heap[index].priority = newPriority
    this.bubbleUp(index)
  }

  bubbleUp(index) {
    // Восстановление свойства кучи после вставки
    const element = this.heap[index]

    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2)
      const parent = this.heap[parentIndex]

      if (element.priority >= parent.priority) break

      // Обмен элементов
      this.heap[parentIndex] = element
      this.heap[index] = parent
      this.positions[element.node] = parentIndex
      this.positions[parent.node] = index

      index = parentIndex
    }
  }

  sinkDown(index) {
    // Восстановление свойства кучи после извлечения
    const length = this.heap.length
    const element = this.heap[index]

    while (true) {
      const leftChildIdx = 2 * index + 1
      const rightChildIdx = 2 * index + 2
      let leftChild, rightChild
      let swap = null

      if (leftChildIdx < length) {
        leftChild = this.heap[leftChildIdx]
        if (leftChild.priority < element.priority) {
          swap = leftChildIdx
        }
      }

      if (rightChildIdx < length) {
        rightChild = this.heap[rightChildIdx]
        if (
          (swap === null && rightChild.priority < element.priority) ||
          (swap !== null && rightChild.priority < leftChild.priority)
        ) {
          swap = rightChildIdx
        }
      }

      if (swap === null) break

      // Обмен элементов
      this.heap[index] = this.heap[swap]
      this.heap[swap] = element
      this.positions[this.heap[index].node] = index
      this.positions[element.node] = swap

      index = swap
    }
  }

  isEmpty() {
    return this.heap.length === 0
  }

  contains(node) {
    return this.positions[node] !== undefined
  }
}

function dijkstraOptimized(graph, start) {
  const distances = {}
  const previous = {}
  const minHeap = new MinHeap()

  // Инициализация
  for (let vertex in graph) {
    if (vertex === start) {
      distances[vertex] = 0
      minHeap.insert(vertex, 0)
    } else {
      distances[vertex] = Infinity
    }
    previous[vertex] = null
  }

  // Множество посещенных вершин
  const visited = new Set()

  // Основной алгоритм
  while (!minHeap.isEmpty()) {
    const { node: current, priority } = minHeap.extractMin()

    // Если уже обработали эту вершину с меньшим расстоянием
    if (visited.has(current)) continue

    // Отмечаем вершину как посещенную
    visited.add(current)

    // Если расстояние бесконечно, вершина недостижима
    if (distances[current] === Infinity) break

    // Для каждого соседа текущей вершины
    for (let neighbor in graph[current]) {
      // Пропускаем уже посещенные вершины
      if (visited.has(neighbor)) continue

      // Вычисляем новое расстояние
      const newDistance = distances[current] + graph[current][neighbor]

      // Если нашли более короткий путь
      if (newDistance < (distances[neighbor] || Infinity)) {
        distances[neighbor] = newDistance
        previous[neighbor] = current

        // Если соседа уже добавили в кучу, обновляем его приоритет
        if (minHeap.contains(neighbor)) {
          minHeap.decreaseKey(neighbor, newDistance)
        } else {
          minHeap.insert(neighbor, newDistance)
        }
      }
    }
  }

  return { distances, previous }
}

Преимущества и недостатки:

✅ Оптимальная временная сложность O((V + E) log V)

✅ Эффективно обрабатывает обновления приоритетов

✅ Хорошо подходит для разреженных графов

❌ Более сложная реализация

❌ Требует больше памяти для хранения позиций элементов

Решение 4: Реализация с использованием встроенной Map для графа 📊

function dijkstra(graph, start) {
  // Создаем словари для хранения расстояний и предыдущих вершин
  const distances = new Map()
  const previous = new Map()

  // Создаем приоритетную очередь для обработки вершин
  const queue = new Set()

  // Инициализация
  for (const vertex of graph.keys()) {
    distances.set(vertex, vertex === start ? 0 : Infinity)
    previous.set(vertex, null)
    queue.add(vertex)
  }

  // Пока очередь не пуста
  while (queue.size > 0) {
    // Находим вершину с минимальным расстоянием
    let minVertex = null
    let minDistance = Infinity

    for (const vertex of queue) {
      const distance = distances.get(vertex)
      if (distance < minDistance) {
        minDistance = distance
        minVertex = vertex
      }
    }

    // Если минимальное расстояние бесконечно, остальные вершины недостижимы
    if (minDistance === Infinity) break

    // Удаляем вершину из очереди
    queue.delete(minVertex)

    // Обновляем расстояния до соседей
    const neighbors = graph.get(minVertex) || new Map()

    for (const [neighbor, weight] of neighbors.entries()) {
      // Если соседа уже обработали, пропускаем
      if (!queue.has(neighbor)) continue

      // Вычисляем новое расстояние
      const distance = distances.get(minVertex) + weight

      // Если нашли более короткий путь
      if (distance < distances.get(neighbor)) {
        distances.set(neighbor, distance)
        previous.set(neighbor, minVertex)
      }
    }
  }

  return { distances, previous }
}

// Пример использования
function createGraph() {
  const graph = new Map()

  // Добавляем вершины и ребра
  graph.set(
    'A',
    new Map([
      ['B', 6],
      ['C', 1],
    ])
  )
  graph.set(
    'B',
    new Map([
      ['A', 6],
      ['D', 2],
      ['E', 3],
    ])
  )
  graph.set(
    'C',
    new Map([
      ['A', 1],
      ['D', 4],
    ])
  )
  graph.set(
    'D',
    new Map([
      ['B', 2],
      ['C', 4],
      ['E', 5],
    ])
  )
  graph.set(
    'E',
    new Map([
      ['B', 3],
      ['D', 5],
    ])
  )

  return graph
}

const graph = createGraph()
const { distances, previous } = dijkstra(graph, 'A')

// Выводим расстояния
for (const [vertex, distance] of distances.entries()) {
  console.log(`Расстояние от A до ${vertex}: ${distance}`)
}

// Восстанавливаем путь до вершины E
function getPath(previous, to) {
  const path = []
  let current = to

  while (current !== null) {
    path.unshift(current)
    current = previous.get(current)
  }

  return path
}

console.log(`Путь от A до E: ${getPath(previous, 'E').join(' -> ')}`)

Особенности:

✅ Использует встроенные структуры данных JavaScript (Map, Set)

✅ Легко расширяемый код с хорошей читаемостью

✅ Включает функцию восстановления пути

❌ Не использует оптимизированную приоритетную очередь

Анализ временной и пространственной сложности

Временная сложность:

Пространственная сложность:

Для всех реализаций: O(V + E), где:

• V — количество вершин
• E — количество рёбер

Ограничения алгоритма Дейкстры

1. Отсутствие отрицательных весов: Алгоритм не работает корректно для графов с отрицательными весами рёбер. В таком случае лучше использовать алгоритм Беллмана-Форда.

2. Плотные графы: Для графов с большим количеством рёбер (близким к V²) базовая реализация может быть эффективнее оптимизированной.

3. Недостижимые вершины: Алгоритм присваивает бесконечные расстояния вершинам, недостижимым из начальной.

Практические применения

1. Навигационные системы

Алгоритм Дейкстры широко используется в GPS-навигаторах и картографических сервисах для поиска оптимальных маршрутов.

2. Сетевая маршрутизация

Протоколы маршрутизации в IP-сетях, такие как OSPF (Open Shortest Path First), основаны на модифицированном алгоритме Дейкстры.

3. Телекоммуникации

Определение оптимальных путей передачи данных в телекоммуникационных сетях.

4. Социальные сети

Поиск кратчайших путей между пользователями (алгоритм "шести рукопожатий").

5. Робототехника

Планирование пути для автономных роботов и беспилотных транспортных средств.

Модификации и улучшения алгоритма

1. Двунаправленный поиск Дейкстры

Одновременный поиск из начальной и конечной вершин, что может значительно ускорить работу:

function bidirectionalDijkstra(graph, start, end) {
  // Инициализация для прямого и обратного поиска
  const forwardDistances = new Map()
  const backwardDistances = new Map()

  // Приоритетные очереди для обоих направлений
  const forwardQueue = new MinHeap()
  const backwardQueue = new MinHeap()

  // Посещенные вершины
  const forwardVisited = new Set()
  const backwardVisited = new Set()

  // Инициализация начальных расстояний
  forwardDistances.set(start, 0)
  backwardDistances.set(end, 0)

  forwardQueue.insert(start, 0)
  backwardQueue.insert(end, 0)

  let bestPath = Infinity
  let intersectionVertex = null

  // Продолжаем, пока обе очереди не пусты
  while (!forwardQueue.isEmpty() && !backwardQueue.isEmpty()) {
    // Если лучший путь уже найден и лучше, чем минимальные расстояния в очередях
    if (
      bestPath <
      forwardQueue.heap[0].priority + backwardQueue.heap[0].priority
    ) {
      break
    }

    // Шаг вперед
    const forward = forwardQueue.extractMin()
    forwardVisited.add(forward.node)

    // Обновляем соседей в прямом направлении
    for (const [neighbor, weight] of graph.get(forward.node).entries()) {
      if (!forwardVisited.has(neighbor)) {
        const newDistance = forwardDistances.get(forward.node) + weight

        if (
          !forwardDistances.has(neighbor) ||
          newDistance < forwardDistances.get(neighbor)
        ) {
          forwardDistances.set(neighbor, newDistance)
          forwardQueue.insert(neighbor, newDistance)

          // Проверяем пересечение с обратным поиском
          if (backwardVisited.has(neighbor)) {
            const pathLength = newDistance + backwardDistances.get(neighbor)
            if (pathLength < bestPath) {
              bestPath = pathLength
              intersectionVertex = neighbor
            }
          }
        }
      }
    }

    // Шаг назад
    const backward = backwardQueue.extractMin()
    backwardVisited.add(backward.node)

    // Обновляем соседей в обратном направлении
    for (const [neighbor, weight] of graph.get(backward.node).entries()) {
      if (!backwardVisited.has(neighbor)) {
        const newDistance = backwardDistances.get(backward.node) + weight

        if (
          !backwardDistances.has(neighbor) ||
          newDistance < backwardDistances.get(neighbor)
        ) {
          backwardDistances.set(neighbor, newDistance)
          backwardQueue.insert(neighbor, newDistance)

          // Проверяем пересечение с прямым поиском
          if (forwardVisited.has(neighbor)) {
            const pathLength = forwardDistances.get(neighbor) + newDistance
            if (pathLength < bestPath) {
              bestPath = pathLength
              intersectionVertex = neighbor
            }
          }
        }
      }
    }
  }

  return bestPath === Infinity ? -1 : bestPath
}

2. A* (А-звёздочка) — расширение алгоритма Дейкстры

Добавляет эвристическую функцию для направления поиска к цели:

function aStar(graph, start, end, heuristic) {
  const openSet = new MinHeap();
  const closedSet = new Set();
  const gScore = new Map(); // Расстояние от старта до вершины
  const fScore = new Map(); // gScore + эвристика
  const cameFrom = new Map();

  // Инициализация
  gScore.set(start, 0);
  fScore.set(start, heuristic(start, end));
  openSet.insert(start, fScore.get(start));

  while (!openSet.isEmpty()) {
    const current = openSet.extractMin().node;

    // Если достигли цели, восстан