Чем алгоритм Беллмана–Форда отличается от Флойда–Уоршелла?

Беллман–Форд ищет кратчайшие пути от одной вершины за `O(V·E)`, Флойд–Уоршелл — между всеми парами вершин за `O(V³)`; оба допускают отрицательные веса рёбер и умеют обнаруживать отрицательные циклы.

Беллман–Форд

• V − 1 раз релаксировать все рёбра: кратчайший путь без циклов содержит не больше V − 1 рёбер.
• Если на V-й итерации что-то ещё улучшилось — есть отрицательный цикл, достижимый из источника.
• Ранний выход, если за итерацию ничего не поменялось.
• Применения: маршрутизация distance-vector (RIP), арбитраж.

Флойд–Уоршелл

ДП по «разрешённым промежуточным вершинам»: d[i][j] = min(d[i][j], d[i][k] + d[k][j]).

const floydWarshall = (n, edges) => {
  const d = Array.from({ length: n }, (_, i) =>
    Array.from({ length: n }, (_, j) => (i === j ? 0 : Infinity)));
  for (const [u, v, w] of edges) d[u][v] = Math.min(d[u][v], w);
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (d[i][k] + d[k][j] < d[i][j]) d[i][j] = d[i][k] + d[k][j];
  const hasNegativeCycle = d.some((row, i) => row[i] < 0);
  return [d, hasNegativeCycle];
};

• Цикл по k обязан быть внешним — перестановка циклов даёт неверный ответ.
• Память O(V²), практичен до V ≈ 500.

Когда что

Один источник — Беллман–Форд. Все пары в плотном графе — Флойд. Все пары в разреженном графе с отрицательными весами — Джонсон: перевзвешивание через Беллмана–Форда и Дейкстра из каждой вершины, O(V·E log V).

Коротко для собеседования

Беллман–Форд нужен для путей из одного источника, когда веса бывают отрицательными, Флойд–Уоршелл — для всех пар сразу в небольшом плотном графе. Оба находят отрицательные циклы — на этом строится поиск валютного арбитража с весами −ln(курс).