Що робить алгоритм Флойда-Уоршелла на графах?

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

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

Алгоритм Флойда-Уоршелла обчислює найкоротші шляхи між усіма парами вершин у зваженому орієнтованому графі (включно з від'ємними вагами ребер, але без від'ємних циклів). Він повертає матрицю найкоротших відстаней, може відновлювати самі шляхи і дозволяє виявити від'ємні цикли (dist[i][i] < 0). Складність: O(V^3) за часом і O(V^2) за пам'яттю.

Детальне пояснення

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

Динамічне програмування: поступово дозволяємо використовувати проміжні вершини {0..k} і покращуємо відомі відстані між кожною парою (i, j).
Основна релаксація: якщо dist[i][k] + dist[k][j] < dist[i][j], оновлюємо dist[i][j] і запам'ятовуємо напрямок для відновлення шляху.
Від'ємні цикли виявляються за умовою dist[v][v] < 0 хоча б для однієї вершини v.

Вхідні дані та угоди

Граф зберігається як матриця суміжності: adj[i][j] - вага ребра i → j, Infinity, якщо ребра немає, 0 на діагоналі.
Підтримуються від'ємні ваги ребер, але алгоритм коректний лише за відсутності від'ємних циклів, досяжних з i в j.
Для неорієнтованого графа ваги симетризують: adj[u][v] = adj[v][u] = w.

Псевдокод

text

dist = adj (скопіювати матрицю)
next[i][j] = j, якщо є ребро i→j, інакше null
для k в [0..n-1]:
  для i в [0..n-1]:
    для j в [0..n-1]:
      якщо dist[i][k] + dist[k][j] < dist[i][j]:
        dist[i][j] = dist[i][k] + dist[k][j]
        next[i][j] = next[i][k]

єВідЦикл = існує v: dist[v][v] < 0
відновитиШлях(u, v): йти по next[u][v], поки не дійдемо до v

Реалізація на JavaScript (з відновленням шляху та перевіркою циклів)

const INF = Infinity;

function floydWarshall(adj) {
  const n = adj.length;
  const dist = Array.from({ length: n }, (_, i) => Array.from({ length: n }, (_, j) => adj[i][j]));
  const next = Array.from({ length: n }, () => Array(n).fill(null));

  // Ініціалізація
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < n; j++) {
      if (i === j && dist[i][j] !== 0) dist[i][j] = 0;
      if (i !== j && dist[i][j] !== INF) next[i][j] = j;
    }
  }

  // Основні потрійні цикли
  for (let k = 0; k < n; k++) {
    for (let i = 0; i < n; i++) {
      const dik = dist[i][k];
      if (dik === INF) continue;
      for (let j = 0; j < n; j++) {
        const dkj = dist[k][j];
        if (dkj === INF) continue;
        const alt = dik + dkj;
        if (alt < dist[i][j]) {
          dist[i][j] = alt;
          next[i][j] = next[i][k];
        }
      }
    }
  }

  // Виявлення від'ємних циклів
  let hasNegativeCycle = false;
  const negativeCycleVertices = [];
  for (let v = 0; v < n; v++) {
    if (dist[v][v] < 0) {
      hasNegativeCycle = true;
      negativeCycleVertices.push(v);
    }
  }

  function reconstructPath(u, v) {
    if (next[u][v] == null) return null; // шляху немає
    const path = [u];
    while (u !== v) {
      u = next[u][v];
      if (u == null) return null; // захист від неузгоджених даних
      path.push(u);
    }
    return path;
  }

  return { dist, next, hasNegativeCycle, negativeCycleVertices, reconstructPath };
}

// Приклад використання
// Вершини: 0,1,2,3
// Ребра: 0→1(3), 0→2(8), 1→2(2), 1→3(5), 2→3(1), 3→1(-2)
const adj = [
  [0,   3,   8,   INF],
  [INF, 0,   2,   5   ],
  [INF, INF, 0,   1   ],
  [INF,-2,   INF, 0   ],
];

const { dist, reconstructPath, hasNegativeCycle } = floydWarshall(adj);
console.log('hasNegativeCycle:', hasNegativeCycle); // false
console.log('dist matrix:');
console.table(dist);

const path03 = reconstructPath(0, 3); // очікувано: [0,1,2,3]
console.log('path 0→3:', path03);

Результат для прикладу (найкоротші відстані)

text

[
  [   0,  3, 5, 6],
  [ INF,  0, 2, 3],
  [ INF, -1, 0, 1],
  [ INF, -2, 0, 0]
]
// Шлях 0→3: 0 → 1 → 2 → 3, вага 6

Виявлення від'ємних циклів

Якщо після виконання алгоритму знайдеться вершина v з dist[v][v] < 0, це означає, що існує від'ємний цикл, досяжний з v. У цьому разі будь-які шляхи, що заходять у цей цикл і виходять з нього, не мають кінцевої мінімальної довжини (їх можна зменшувати нескінченно). На практиці:

Зупиняйте відновлення шляху, якщо маршрут заходить у підграф, досяжний від від'ємного циклу.
Іноді додатково «проштовхують» -Infinity вздовж ребер, досяжних з від'ємних циклів, щоб явно позначити такі відстані як необмежено малі.

Складність і коли застосовувати

Час: O(V^3). Пам'ять: O(V^2).
Добре підходить для щільних графів і коли потрібен результат для всіх пар вершин.
Для розріджених графів і багатьох запитів шляху частіше вигідніші Джонсон або багаторазовий Дейкстра (якщо немає від'ємних ребер).

Відновлення шляху

Зберігайте матрицю next: next[i][j] = перша вершина після i на найкоротшому шляху до j.
Стартуйте з u, поки u != v: u = next[u][v], додаючи вершини до списку.

Зв'язок з алгоритмом Уоршелла (транзитивне замикання)

Якщо замість чисел використовувати булеві значення (чи є шлях), отримуємо алгоритм Уоршелла для транзитивного замикання: reach[i][j] |= reach[i][k] && reach[k][j]. Це той самий шаблон потрійного циклу.

Часті питання на співбесіді

Чи підтримує від'ємні ваги? - Так. Від'ємні цикли не підтримуються (їх можна лише виявити).
Що повертає? - Матрицю dist усіх найкоротших відстаней; опціонально - матрицю next для відновлення шляху.
Складність? - O(V^3) час, O(V^2) пам'ять.
Коли краще Дейкстра? - Коли граф без від'ємних ребер і потрібні шляхи з однієї вершини; для всіх пар Дейкстру запускають V разів або використовують Джонсон.

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

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

Premium

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