Запропонувати правку

Покращити цю статтю

Допрацюйте відповідь до «Що робить алгоритм Беллмана-Форда (Bellman-Ford) на графах?». Ваші зміни проходять модерацію перед публікацією.

Потрібне підтвердження

Контент

Що ви змінюєте

Заголовок (UA)

Коротка відповідь (UA)

Показується над повною відповіддю для швидкого нагадування.

Відповідь (UA)

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

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

## Детально

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

### Що вміє

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

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

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

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

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

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

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

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

Вершини: 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 найкоротші шляхи шукаються швидше через топологічний порядок.

Markdown · перетягуйте зображення · ⌘B / ⌘I шорткати894 слів

Для рев’юера

Примітка для модератора (необов’язково)

Бачить лише модератор. Прискорює рев’ю.