Алгоритм Bellman‑Ford

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

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

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

Аналогія

Уявіть, що ви плануєте подорож по місту з різними дорогами, де деякі дороги можуть бути «поганими» (негативними). Bellman‑Ford – це як розповідати кожному водієві про новий найкоротший маршрут, повторюючи це кілька разів, доки всі не дізнаються про найкоротший шлях.

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

• Граф має можливі негативні ваги ребер.
• Потрібно знайти найкоротші шляхи з однієї вершини до всіх інших.
• Необхідно перевірити наявність негативних циклів, що доступні з початкової вершини.
• Кількість вершин невелика (наприклад, до кількох тисяч), бо алгоритм O(V·E).
• Коли інші алгоритми (Dijkstra) недоступні через негативні ваги.

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

1. Ініціалізувати відстані: до початкової вершини 0, до всіх інших нескінченність.
2. Для кожної вершини (|V|-1) разів:
   1. Перебрати всі ребра графу.
   2. Якщо відстань до вершини‑початку + вага ребра < відстань до вершини‑кінця, оновити цю відстань.
3. Після ітерацій пройти ще один раз по всіх ребрах: якщо можна зменшити відстань, виявлено негативний цикл.

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

Відстані: [0, ∞, ∞]
Ітерація 1:
  (A→B, w=4) → d[B]=4
  (B→C, w=-2) → d[C]=2
Ітерація 2:
  (C→A, w=1) → d[A] не змінюється
  (B→C, w=-2) → d[C] не змінюється
Немає негативного циклу.

Складність

Часова складність: O(V·E), бо |V|-1 ітерацій по всіх ребрах. Пам’ятова складність: O(V), оскільки зберігаються лише масиви відстаней.

Код (js)

// Функція Bellman‑Ford: знаходить найкоротші шляхи з однієї вершини
function bellmanFord(vertices, edges, source) {
  // ініціалізуємо масив відстаней: до початкової вершини 0, інші – нескінченність
  const dist = new Array(vertices).fill(Infinity);
  dist[source] = 0;

  // |V|‑1 разів проходимо по всіх ребрах, оновлюємо відстані
  for (let i = 0; i < vertices - 1; i++) {
    // перебираємо кожне ребро (u, v, w)
    for (const [u, v, w] of edges) {
      // якщо шлях через u до v коротший, оновлюємо
      if (dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
      }
    }
  }

  // перевірка наявності негативного циклу: ще один прохід по ребрах
  for (const [u, v, w] of edges) {
    if (dist[u] + w < dist[v]) {
      throw new Error('Граф містить негативний цикл, доступний з вершини ' + source);
    }
  }

  return dist; // повертаємо масив найкоротших відстаней
}

// Тестовий приклад
const vertices = 5;
const edges = [
  [0, 1, 6],
  [0, 2, 7],
  [1, 2, 8],
  [1, 3, 5],
  [1, 4, -4],
  [2, 3, -3],
  [2, 4, 9],
  [3, 1, -2],
  [4, 0, 2],
  [4, 3, 7]
];
console.log(bellmanFord(vertices, edges, 0)); // очікуваний результат: [0, 2, 7, 4, -2]

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

1. Неправильна ініціалізація відстаней – забувають встановити нескінченність для всіх вершин, крім початкової. Це призводить до помилкових оновлень.
2. Відсутність перевірки негативного циклу – алгоритм повертає некоректні відстані, якщо в графі є негативний цикл. Завжди додайте останній прохід.
3. Використання «Infinity» як числа – при додаванні до Infinity результат залишається Infinity, тому перевірка dist[u] + w < dist[v] працює правильно.
4. Перевищення меж масиву – індекси вершин повинні бути у діапазоні [0, V‑1]. Перевірте вхідні дані.
5. Оптимізація – якщо граф без негативних циклів, можна зупинити ітерації, коли жодне ребро не оновлює відстань (early exit).

Перевір себе

1. Яка складність Bellman‑Ford у найгіршому випадку? (O(V·E))
2. Чому Bellman‑Ford потрібен, коли Dijkstra працює швидше? (тому що Dijkstra не підтримує негативні ваги).