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

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

Сложность: время O(V^3); память: O(V^2) под матрицу расстояний. Прост в реализации и удобен для плотных графов небольшого размера.

def floyd_warshall(dist):  # dist — матрица V x V
    n = len(dist)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                if dist[i][k] + dist[k][j] < dist[i][j]:
                    dist[i][j] = dist[i][k] + dist[k][j]
    return dist