← Назад к графовым алгоритмам

Алгоритм Флойда-Уоршелла

Поиск кратчайших расстояний между всеми парами вершин

🐍 Python
n = int(input())
D = [list(map(int, input().split())) for _ in range(n)]

for k in range(n):
    for i in range(n):
        for j in range(n):
            D[i][j] = min(D[i][j], D[i][k] + D[k][j])

for row in D:
    print(*row)
⚙️ C++
#include <bits/stdc++.h>
using namespace std;

const int INF = 1e9;

int main() {
    int n;
    cin >> n;
    
    vector<vector<int>> D(n, vector<int>(n));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> D[i][j];
            if (D[i][j] == -1) D[i][j] = INF;
        }
    }
    
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (D[i][k] < INF && D[k][j] < INF) {
                    D[i][j] = min(D[i][j], D[i][k] + D[k][j]);
                }
            }
        }
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (D[i][j] >= INF) cout << "-1 ";
            else cout << D[i][j] << " ";
        }
        cout << "\n";
    }
    
    return 0;
}

Как работает алгоритм Флойда-Уоршелла?

Алгоритм Флойда-Уоршелла находит кратчайшие расстояния между всеми парами вершин во взвешенном графе (с возможными отрицательными рёбрами, но без отрицательных циклов).

Основная идея

Алгоритм использует динамическое программирование. Пусть D[i][j] — текущее известное кратчайшее расстояние от вершины i до вершины j.

На каждом шаге k мы пытаемся улучшить путь между всеми парами вершин, используя вершину k как промежуточную:

D[i][j] = min(D[i][j], D[i][k] + D[k][j])

Тройной вложенный цикл:

Если путь через вершину k короче текущего, мы обновляем расстояние.

Временная сложность: O(n³) — три вложенных цикла по n вершин.

Пространственная сложность: O(n²) — матрица расстояний.

Важные замечания

Пример работы

Рассмотрим граф из 4 вершин с матрицей весов:

  0  5  9  4
  5  0  2  ∞
  9  2  0  3
  4  ∞  3  0

Пошаговое выполнение:

Шаг k=0 (промежуточная вершина 0):
  Проверяем пути через вершину 0
  D[2][1] = min(2, 9+5=14) → 2
  D[3][1] = min(∞, 4+5=9) → 9
  D[3][2] = min(3, 4+9=13) → 3

Шаг k=1 (промежуточная вершина 1):
  D[0][2] = min(9, 5+2=7) → 7
  D[0][3] = min(4, 5+9=14) → 4
  D[2][0] = min(9, 2+5=7) → 7
  D[2][3] = min(3, 2+9=11) → 3
  D[3][0] = min(4, 9+5=14) → 4
  D[3][2] = min(3, 9+2=11) → 3

Шаг k=2 (промежуточная вершина 2):
  D[0][1] = min(5, 7+2=9) → 5
  D[0][3] = min(4, 7+3=10) → 4
  D[1][0] = min(5, 2+7=9) → 5
  D[1][3] = min(∞, 2+3=5) → 5
  D[3][0] = min(4, 3+7=10) → 4
  D[3][1] = min(9, 3+2=5) → 5

Шаг k=3 (промежуточная вершина 3):
  D[0][1] = min(5, 4+5=9) → 5
  D[0][2] = min(7, 4+3=7) → 7
  D[1][0] = min(5, 5+4=9) → 5
  D[1][2] = min(2, 5+3=8) → 2
  D[2][0] = min(7, 3+4=7) → 7
  D[2][1] = min(2, 3+5=8) → 2

Результат:
  0  5  7  4
  5  0  2  5
  7  2  0  3
  4  5  3  0

Итоговая матрица кратчайших расстояний между всеми парами вершин

Попробовать алгоритм онлайн

Введите матрицу смежности (n×n, где ∞ = -1 или большое число):

Результат появится здесь...