Floyd Warshall Algorithm

СреднеКратчайшие пути Динамическое программирование

+10

Задан ориентированный граф с n узлами, пронумерованными от 0 до n-1, в виде матрицы размера n на n: matrix[i][j] — это вес ребра от узла i к узлу j или -1, если ребра нет, а matrix[i][i] равно 0. Длина пути — это сумма весов его рёбер.

Верните матрицу размера n на n, в которой элемент [i][j] — это длина кратчайшего пути от узла i до узла j или -1, если из узла i нельзя достичь узла j.

Функция

shortestDistances(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: веса рёбер: matrix[i][j] — это вес ребра из i в j или -1, если ребра нет
Возвращаетinteger-2d-array: кратчайшее расстояние для каждой пары узлов, -1, если пути нет

Ограничения

1 ≤ n ≤ 100, где n = matrix.length = matrix[i].length
matrix[i][i] = 0
Для i ≠ j значение matrix[i][j] равно -1 (ребра нет) или 0 ≤ matrix[i][j] ≤ 1000.
Рёбра направлены в одну сторону: matrix[i][j] и matrix[j][i] независимы.

Примеры

Ввод: matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]
Вывод: [[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]
Пояснение: Через узел 1 узел 0 достигает узла 2 за 6 вместо 11, а узла 3 — за 9. Узел 1 достигает узла 0 через узел 2 за 3. Из узла 3 ничего не выходит, поэтому в его строке стоит -1 вне диагонали.

Ввод: matrix = [[0, 6, 1], [-1, 0, -1], [-1, 0, 0]]
Вывод: [[0, 1, 1], [-1, 0, -1], [-1, 0, 0]]
Пояснение: Ребро из 2 в 1 имеет вес 0, поэтому путь 0 → 2 → 1 стоит 1, что меньше прямого пути стоимостью 6. Из узла 1 не выходит ни одного ребра и в узел 0 не входит ни одного ребра, поэтому для этих пар остаётся -1.

Дополнительный вопрос

После построения таблицы одно ребро становится дешевле. Можешь обновить все расстояния за O(n²), вместо того чтобы снова запускать циклы O(n³)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Тебе нужен кратчайший путь для каждой пары узлов. Алгоритм Флойда — Уоршелла находит все n² ответов с помощью одного тройного цикла. На каждом раунде маршруты могут проходить ещё через один узел, а для каждой пары выполняется одно сравнение: лучшего маршрута на данный момент с маршрутом через новый узел.

Продлевайте каждый маршрут на одно ребро, пока ничего не изменится

Верно, но не успевает на самых больших тестах

Идея

Начни с матрицы и на каждом проходе увеличивай каждый маршрут на одно ребро: маршрут из i в m плюс ребро m → j — это маршрут из i в j, который сохраняется, если он короче. Повторяй, пока за проход ничего не меняется.

После p проходов найдены все кратчайшие маршруты длиной до p+1 рёбер. Ни один вес не отрицателен, поэтому некоторый кратчайший маршрут не содержит циклов и состоит не более чем из n-1 рёбер, а проходы останавливаются, когда все расстояния окончательно определены. Один проход — это n³ = 10^6 шагов для 100 узлов, а длинная цепочка кратчайших маршрутов требует до n проходов: O(n⁴), до 10^8 шагов.

Алгоритм

Скопируй matrix в dist.
Для каждого i, m и j: если существуют и dist[i][m], и matrix[m][j], вычисли их сумму.
Если dist[i][j] равно -1 или больше суммы, сохрани сумму и запомни, что проход что-то изменил.
Повторяй проход, пока он не перестанет что-либо менять, затем верни dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the routes of one edge; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    changed = True
    while changed:
        changed = False
        # One pass: a route from i that ends at m may grow by the edge m -> j.
        for i in range(n):
            for m in range(n):
                if dist[i][m] == -1:
                    continue
                for j in range(n):
                    edge = matrix[m][j]
                    if edge == -1:
                        continue
                    via = dist[i][m] + edge
                    if dist[i][j] == -1 or via < dist[i][j]:
                        dist[i][j] = via
                        changed = True
    return dist

Флойд — Уоршелл: добавляем ещё одну остановку за раунд

Идея

Ограничьте узлы, на которых маршрут может останавливаться между его концами. Изначально таблица содержит матрицу — маршруты без остановок. После раунда k значение dist[i][j] — это кратчайший маршрут, все остановки которого находятся среди узлов от 0 до k, а последний раунд даёт ответ.

В раунде k наилучший маршрут, который также может проходить через k, либо пропускает k — и тогда он уже есть в таблице, — либо проходит через k один раз, поскольку веса неотрицательны. Его две части проходят только через узлы от 0 до k-1, поэтому это dist[i][k] и dist[k][j].

В первом примере раунд 1 заменяет прямой маршрут длиной 11 от узла 0 до узла 2 на маршрут длиной 6. В раунде 2 расстояние от узла 0 до узла 3 становится равным 6 + 3 = 9, причём остановка в узле 1 находится внутри маршрута длиной 6.

Достаточно одной таблицы: строка k и столбец k не меняются в раунде k, потому что dist[k][k] равно 0.

Алгоритм

Скопируй matrix в dist; -1 означает, что маршрут пока не найден.
Для k от 0 до n-1 и для каждого i и j: пропусти эту пару, если dist[i][k] или dist[k][j] равно -1.
В противном случае вычисли via = dist[i][k] + dist[k][j].
Если dist[i][j] равно -1 или больше, чем via, присвой ему значение via.
Верни dist.

def shortestDistances(matrix):
    n = len(matrix)
    # dist starts as the direct edges; -1 means no route found yet.
    dist = [row[:] for row in matrix]
    # After round k, dist[i][j] is the cheapest route whose stops all lie in 0..k.
    for k in range(n):
        for i in range(n):
            if dist[i][k] == -1:
                continue
            for j in range(n):
                if dist[k][j] == -1:
                    continue
                via = dist[i][k] + dist[k][j]
                if dist[i][j] == -1 or via < dist[i][j]:
                    dist[i][j] = via
    return dist

Ловушки и крайние случаи

Прибавлять -1, как если бы это был вес: -1 + 5 = 4 выглядит как маршрут. Сначала проверьте обе части и считайте -1 в dist[i][j] хуже любого маршрута.
Помещать цикл по k внутрь. Маршруты через остановки от 0 до k-1 должны быть окончательно определены до того, как будет предложен узел k.
Использовать наибольшее значение int как бесконечность: сложение двух таких значений приводит к переполнению 32-битного int и отрицательному расстоянию. Реальное расстояние не превышает 99 × 1000 = 99,000, поэтому 10^9 безопасно, так как 2 × 10^9 меньше 2^31-1.
Предполагать, что рёбра направлены в обе стороны. Во втором примере из узла 0 можно попасть в узел 1, но из узла 1 нельзя попасть никуда.
Запускать поиск в ширину, который не учитывает веса: в первом примере он выдаёт 11 для пути из узла 0 в узел 2, а не 6.

Частые вопросы3

Какова временная сложность алгоритма Флойда — Уоршелла?

Время O(n³) для n узлов: три вложенных цикла по узлам, с одним сложением и одним сравнением на шаг, 10^6 шагов для 100 узлов. Объём памяти — O(n²) для таблицы расстояний, которую можно обновлять на месте.

Работает ли алгоритм Флойда — Уоршелла с отрицательными весами рёбер?

Да, если нет отрицательного цикла — цикла, сумма весов которого меньше 0. При наличии отрицательного цикла кратчайшие пути не определены, и это видно по таблице: некоторые значения dist[i][i] оказываются меньше 0.

Когда следует использовать алгоритм Флойда — Уоршелла вместо алгоритма Дейкстры?

Используй алгоритм Флойда — Уоршелла для каждой пары узлов в плотном графе размером до нескольких сотен узлов. Запуск алгоритма Дейкстры из каждого узла требует O(n³) операций при использовании массива и O(n · E log n) при использовании кучи, что выгоднее для больших разреженных графов. Алгоритму Флойда — Уоршелла не нужна куча, и он допускает отрицательные рёбра, в отличие от алгоритма Дейкстры.

def shortestDistances(matrix):
    # Напишите здесь код

Тест #1

Тест #2

Аргумент

matrix = [[0, 4, 11, -1], [-1, 0, 2, 9], [1, -1, 0, 3], [-1, -1, -1, 0]]

Ожидаемый вывод

[[0, 4, 6, 9], [3, 0, 2, 5], [1, 5, 0, 3], [-1, -1, -1, 0]]