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

Повне пояснення

Коротке пояснення

Алгоритм Дейкстри шукає найкоротший шлях від однієї вершини до всіх інших у графі з невід’ємними вагами, використовуючи пріоритетну чергу для вибору вершини з найменшою відомою довжиною.

Аналогія

Уявіть, що ви плануєте подорож по місту: кожен вузол – це пункт, а ваги – це час проїзду. Алгоритм спочатку вибирає найкоротший шлях до найближчого пункту, потім розширює маршрут, додаючи нові найкоротші шляхи.

Коли застосовувати

• Знайти найкоротший шлях у графі з невід’ємними вагами.
• Потрібно обчислити відстані до всіх вершин з однієї точки.
• Граф не містить циклів із негативними вагами.
• Вхідний граф представлений у вигляді списку суміжності або матриці.
• Потрібна ефективність для великих графів з десятками тисяч вершин.

Кроки алгоритму

1. Ініціалізувати відстані: source = 0, інші – нескінченність.
2. Додати усі вершини до пріоритетної черги з їхніми відстанями.
3. Витягнути вершину з найменшою відстанню (current).
4. Для кожного сусіда current: обчислити нову відстань через current.
5. Якщо нова відстань менша, оновити її і додати сусіда в чергу.
6. Повторювати кроки 3–5, доки черга не порожня.

Візуальна інтуїція (текстова)

Вершини: A, B, C
Відстані: [A=0, B=∞, C=∞]
Черга: (A,0)

Витяг A → B (2), C (5) → оновити: [A=0, B=2, C=5]
Черга: (B,2), (C,5)

Витяг B → C (1) → нова: 2+1=3 <5 → оновити C
Черга: (C,3)

Складність

Часова складність: O((V+E) log V), де V – кількість вершин, E – ребер, завдяки пріоритетній черзі. Пам’ятна складність: O(V+E) для зберігання графу та відстаней.

Код (js)

// Алгоритм Дейкстри для графу, представленного списком суміжності
function dijkstra(graph, start) {
  // Ініціалізуємо відстані: до всіх вершин – нескінченність
  const distances = {};
  for (const vertex in graph) {
    distances[vertex] = Infinity; // ініціалізація
  }
  distances[start] = 0; // стартова вершина має довжину 0

  // Пріоритетна черга (міні-heap) – реалізована як масив з простим пошуком
  const priorityQueue = [];
  function enqueue(vertex, priority) {
    priorityQueue.push({ vertex, priority });
    // Сортуємо за зростанням пріоритету (мінімальна відстань на початку)
    priorityQueue.sort((a, b) => a.priority - b.priority);
  }

  enqueue(start, 0); // додаємо стартову вершину

  while (priorityQueue.length > 0) {
    // Витягуємо вершину з найменшою відстанню
    const { vertex: currentVertex, priority: currentDistance } = priorityQueue.shift();

    // Якщо знайдено новішу (меншу) відстань, пропускаємо
    if (currentDistance > distances[currentVertex]) continue;

    // Перебираємо сусідів поточної вершини
    const neighbors = graph[currentVertex];
    for (const neighbor of neighbors) {
      const { vertex: nextVertex, weight } = neighbor;
      const newDistance = distances[currentVertex] + weight; // нова відстань через current
      if (newDistance < distances[nextVertex]) {
        // Оновлюємо відстань і додаємо в чергу
        distances[nextVertex] = newDistance;
        enqueue(nextVertex, newDistance);
      }
    }
  }

  return distances; // повертаємо таблицю мінімальних довжин
}

// Тестовий приклад
const graph = {
  A: [{ vertex: 'B', weight: 2 }, { vertex: 'C', weight: 5 }],
  B: [{ vertex: 'A', weight: 2 }, { vertex: 'C', weight: 1 }],
  C: [{ vertex: 'A', weight: 5 }, { vertex: 'B', weight: 1 }],
};
console.log(dijkstra(graph, 'A')); // очікуваний результат: { A: 0, B: 2, C: 3 }

Типові помилки і поради

1. Використання масиву як черги без сортування – призводить до O(V^2) часу. Використайте heap або бібліотеку.
2. Забудьте оновити відстань у черзі – нові значення не будуть враховані. Завжди додавайте вершину після оновлення.
3. Невірне оброблення графу з циклом – алгоритм працює лише для невід’ємних ваг. Перевірте дані перед запуском.
4. Не ініціалізувати відстань до всіх вершин – залишить undefined, що призведе до NaN.
5. Оптимізація – використайте Set для відстеження оброблених вершин, щоб уникнути зайвих ітерацій.

Перевір себе

1. Яка складність алгоритму Дейкстри при використанні міні-heap?
2. Чому граф не повинен містити негативних ваг для правильного виконання алгоритму?