Алгоритм Першого річка – пошук мінімального шляху в графі

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

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

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

Аналогія

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

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

• граф із невід’ємними вагами;
• потрібен найкоротший шлях від однієї вершини до всіх інших;
• граф не надто великий, щоб використовувати O(V^2) варіант;
• потрібна швидка реакція на запити про шлях.

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

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

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

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

Витяг A → B: нова відстань 5 → оновити
Черга: (B,5)

Витяг B → C: нова відстань 9 → оновити
Черга: (C,9)

Складність

Часова складність: O((V+E) log V) з пріоритетною чергою; просторовий: O(V+E). У найгіршому випадку, коли використовується простий масив замість черги, складність підвищується до O(V^2).

Код (js)

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

  // 2. Створюємо пріоритетну чергу (масив + сортування)
  const priorityQueue = [];
  for (const vertex in graph) {
    priorityQueue.push({ node: vertex, distance: distances[vertex] });
  }

  // 3. Поки черга не порожня
  while (priorityQueue.length > 0) {
    // сортуємо за відстанню, щоб отримати вершину з мінімальною
    priorityQueue.sort((a, b) => a.distance - b.distance);
    const { node: currentVertex, distance: currentDistance } = priorityQueue.shift();

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

    // 4. Перевіряємо сусідів
    for (const [neighbor, weight] of graph[currentVertex]) {
      const newDistance = distances[currentVertex] + weight;
      if (newDistance < distances[neighbor]) {
        // 5. Оновлюємо відстань
        distances[neighbor] = newDistance;
        // 6. Оновлюємо позицію у черзі
        const index = priorityQueue.findIndex(v => v.node === neighbor);
        if (index !== -1) {
          priorityQueue[index].distance = newDistance;
        } else {
          priorityQueue.push({ node: neighbor, distance: newDistance });
        }
      }
    }
  }

  return distances;
}

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

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

1. Використання простого масиву замість черги – призводить до O(V^2) часу. Використайте PriorityQueue або бібліотеку.
2. Не оновлювати відстань, якщо нова більша – це знижує ефективність. Перевірте умову newDistance < distances[neighbor].
3. Забудьте про відсутність ваг – у графі з негативними вагою Дейкстра не працює. Перевірте дані перед запуском.
4. Не обробляйте вершини, що вже були «закриті» – це можна уникнути перевіркою currentDistance > distances[currentVertex].
5. Оптимізація – використайте двійкову купу (binary heap) замість сортування масиву, щоб зменшити час на O((V+E) log V).

Перевір себе

1. Чому Дейкстра не працює з негативними вагами?
2. Яка складність у найгіршому випадку, якщо використовувати простий масив замість купи?