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

Все кратчайшие пути сразу: матрица, пересчитываемая через k-ю вершину.

время O(V³)память O(V²)уровень: начальный

Что происходит сейчас0/0

Нажмите Play, чтобы запустить сценарий

TypeScript — активная строка подсвечена шагом

1function floydWarshall(w: number[][]): number[][] {
2  const n = w.length
3  const d = w.map((row) => row.slice())
4 
5  for (let k = 0; k < n; k++) {
6    for (let i = 0; i < n; i++) {
7      for (let j = 0; j < n; j++) {
8        if (d[i][k] + d[k][j] < d[i][j]) {
9          d[i][j] = d[i][k] + d[k][j]
10        }
11      }
12    }
13  }
14 
15  return d
16}

Проблема

Все кратчайшие пути сразу: матрица, пересчитываемая через k-ю вершину.

Что вы видите

Матрица d[i][j]: стоит ли ехать через k, если это дешевле?

Как это работает

Динамическое программирование по промежуточной вершине: O(V³), зато ответ для всех пар и отрицательные рёбра допустимы (без отрицательных циклов).

Пошаговый разбор

01
Через k
d[i][k] + d[k][j] против d[i][j].
02
Обновление
Дешевле — пишем.
03
Итог
Матрица всех пар расстояний.

Complexity и ограничения

time

O(V³)

space

O(V²)

См. complexity в шапке страницы.

Edge cases

Пустой вход
Корректно завершается без лишних шагов.
Вырожденный случай
Минимум работы — сразу ответ.

Где встречается в реальности

Продукт

Классический приём в реальных системах.

Собеседования

Стандартный вопрос на понимание структуры.

Связанные алгоритмы

Алгоритм Дейкстры Беллман-Форд

Shorts

«Все пути сразу: одна матрица на всё»

Тот же сценарий StepSequence в вертикальной композиции — с safe zones и записью WebM ниже на странице.

Shorts 9:16

Вертикальная композиция строится той же последовательностью шагов, что и страница: safe zones отмечены пунктиром (там живёт UI платформ), биты сценария подсвечиваются по прогрессу. Кнопка записи сохраняет WebM — детерминированная StepSequence даёт воспроизводимый ролик без монтажа.

Все пути сразу: одна матрица на всё

Нажмите Play

Бит 1/6 · 0–2 с

Hook

script-setup.ru/algorithms/floyd-warshall