Що робить алгоритм Беллмана-Форда (Bellman-Ford) на графах?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Алгоритм Беллмана-Форда знаходить найкоротші шляхи від однієї початкової вершини у зваженому орієнтованому графі, коректно працює з від'ємними вагами і вміє виявляти досяжні від'ємні цикли.

Це класичний алгоритм найкоротших шляхів з однієї вершини, який послідовно «розслаблює» (покращує) оцінки відстаней, проходячи по всіх ребрах графа. На відміну від Дейкстри, він справляється з від'ємними вагами і може сказати, що коректних найкоротших шляхів не існує, якщо з джерела досяжний від'ємний цикл.

Що вміє

Знаходить найкоротші шляхи з однієї вершини (single-source shortest paths, SSSP).
Коректно працює з від'ємними вагами ребер.
Виявляє досяжні з джерела від'ємні цикли (із сумарною від'ємною вагою).
Підходить для орієнтованих графів; для неорієнтованих кожне ребро представляють двома напрямленими.

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

Потрібні найкоротші шляхи за наявності від'ємних ваг.
Потрібно виявити від'ємні цикли, досяжні з джерела.
Граф не надто великий (алгоритм повільніший за Дейкстру).

Обмеження і складність

Час: O(V · E), де V - кількість вершин, E - кількість ребер.
Пам'ять: O(V).
Якщо від'ємний цикл досяжний з джерела, коректних кінцевих відстаней не існує - алгоритм це виявляє і повідомляє.

Ідея алгоритму

Ініціалізація: відстань до джерела = 0, до інших = +∞; батьки невідомі.
Повторити V-1 разів: пройти по всіх ребрах (u → v, w) і спробувати покращити dist[v] через u. Це «розслаблення» ребра: якщо dist[u] + w < dist[v], оновити dist[v] і запам'ятати батька v = u.
Перевірка на від'ємний цикл: зробити ще один прохід по ребрах. Якщо якась відстань усе ще покращується, отже, існує досяжний від'ємний цикл.

Приклад (без від'ємного циклу)

Вершини: S=0, A=1, B=2, C=3. Ребра: S→A (4), S→B (5), A→B (−2), B→C (3), A→C (4).

Початок: dist = [0, +∞, +∞, +∞].
Після ітерацій: dist[A]=4 (S→A), dist[B]=2 (S→A→B з вагами 4 + (−2)), dist[C]=5 (краще через B: 2 + 3).

Приклад виявлення від'ємного циклу

Вершини: S=0, A=1, B=2, C=3. Ребра: S→A (1), A→B (1), B→C (1), C→A (−4). Цикл A→B→C→A має сумарну вагу −2, алгоритм виявить його на додатковому проході.

Код на JavaScript (ES6)

javascript

/*
Bellman-Ford: найкоротші шляхи з джерела s у графі з n вершинами і списком ребер.
Ребра: масив об'єктів { u, v, w } - з u в v з вагою w.
Повертає: { dist, parent, negativeCycle, cycle }.
*/
function bellmanFord(n, edges, s) {
  const INF = Number.POSITIVE_INFINITY;
  const dist = Array(n).fill(INF);
  const parent = Array(n).fill(null);
  dist[s] = 0;

  // V-1 ітерація релаксацій
  for (let i = 0; i < n - 1; i++) {
    let updated = false;
    for (const { u, v, w } of edges) {
      if (dist[u] !== INF && dist[u] + w < dist[v]) {
        dist[v] = dist[u] + w;
        parent[v] = u;
        updated = true;
      }
    }
    if (!updated) break; // ранній вихід, якщо вже стабільно
  }

  // Перевірка на від'ємний цикл (дод. прохід)
  let x = -1;
  for (const { u, v, w } of edges) {
    if (dist[u] !== INF && dist[u] + w < dist[v]) {
      dist[v] = dist[u] + w; // формально ще покращилося
      parent[v] = u;
      x = v; // вершина, покращена на (V)-й ітерації
    }
  }

  let negativeCycle = false;
  let cycle = [];
  if (x !== -1) {
    negativeCycle = true;
    // Знаходимо вершину, гарантовано розташовану на циклі
    let y = x;
    for (let i = 0; i < n; i++) y = parent[y];

    // Відновлюємо цикл, йдучи по parent до повернення в y
    const stack = [];
    let cur = y;
    do {
      stack.push(cur);
      cur = parent[cur];
    } while (cur !== y && stack.length <= n + 5);
    stack.push(y);
    cycle = stack.reverse(); // цикл як послідовність вершин
  }

  return { dist, parent, negativeCycle, cycle };
}

// Приклад використання (без від'ємного циклу)
const n1 = 4; // 0:S, 1:A, 2:B, 3:C
const edges1 = [
  { u: 0, v: 1, w: 4 },
  { u: 0, v: 2, w: 5 },
  { u: 1, v: 2, w: -2 },
  { u: 2, v: 3, w: 3 },
  { u: 1, v: 3, w: 4 },
];
console.log('Example 1:', bellmanFord(n1, edges1, 0));

// Приклад з від'ємним циклом
const n2 = 4; // 0:S, 1:A, 2:B, 3:C
const edges2 = [
  { u: 0, v: 1, w: 1 },
  { u: 1, v: 2, w: 1 },
  { u: 2, v: 3, w: 1 },
  { u: 3, v: 1, w: -4 }, // цикл A->B->C->A із сумою -2
];
console.log('Example 2:', bellmanFord(n2, edges2, 0));

Розбір коду

Параметри: n - кількість вершин (індекси 0..n-1), edges - список ребер {u,v,w}, s - джерело.
dist - масив відстаней; parent - для відновлення шляхів.
negativeCycle - прапорець наявності досяжного від'ємного циклу; cycle - одна знайдена петля (послідовність вершин).
Оптимізація: ранній вихід, якщо на ітерації не було покращень.

Порівняння з Дейкстрою в двох словах

Дейкстра: швидша (O((V+E) log V)), але працює лише з невід'ємними вагами (без спеціальних прийомів).
Беллман-Форд: повільніший (O(V·E)), але підтримує від'ємні ваги і виявляє від'ємні цикли.

Важливі нюанси на співбесіді

Найчастіше граф представляють списком ребер: це зручно, оскільки алгоритм ітерується по ребрах.
Ініціалізація: dist[source]=0, інші +∞; parent[source]=null.
Якщо від'ємний цикл досяжний, коректних фінальних відстаней немає; потрібно або повідомити про це, або позначити відповідні вершини як «мінус нескінченність».
Можна прискорити в «розріджених» графах через ранній вихід за відсутності оновлень.
Для DAG найкоротші шляхи шукаються швидше через топологічний порядок.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.