Оптимизируйте Floyd-Warshall для симметричной матрицы смежности

После некоторой мысли я придумал:

for (int k = 0; k < N; ++k)
    for (int i = 0; i < N; ++i)
        for (int j = 0; j <= i; ++j)
            dist[j][i] = dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

Теперь, конечно, мы оба должны показывать, что правильно и быстрее.

Правильность труднее доказать, поскольку она зависит от доказательства Флойд-Варшалла, который нетривиален. Здесь приведено довольно хорошее доказательство: Доказательство Floyd-Warshall

. Входная матрица симметричен . Теперь остальная часть доказательства использует модифицированную доказательство Floyd-Warshall, чтобы показать, что порядок расчетов в 2 внутренних цикла не имеет значения, и что график остается симметричным после каждого шага. Если мы покажем оба этих условия, верны, то оба алгоритма делают то же самое.

Давайте определим DIST [I] [J] [K] , как расстояние от I на j , используя только с использованием только вершины в вершинах {0, ..., k} как промежуточные вершины на пути из I к j .

dist [i] [j] [k-1] определяется как вес края из I на j . Если между этим весом нет края, принимается бесконечность.

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

dist[i][j][k] = min(dist[i][j][k-1], dist[i][k][k-1] + dist[k][j][k-1])

Теперь в расчете dist [i] [k] [K] (и аналогично для dist [k ] [I] [K] ) ):

dist[i][k][k] = min(dist[i][k][k-1], dist[i][k][k-1] + dist[k][k][k-1])

Теперь с dist [k] [k] [k-1] не может быть отрицательным (или у нас будет негативная петля На графике) это означает, что dist [i] [k] [k] = dist [i] [k] [k-1] . Поскольку если dist [k] [k] [k-1] = 0 , то оба параметра одинаковы, в противном случае выбран первый параметр min () .

Так что теперь, потому что dist [i] [k] [k] = dist [i] [k] [k-1] , при расчете dist [i] [j] K] Это не имеет значения, если dist [i] [k] или dist [k] [j] уже разрешают k в своих путях Отказ С DIST [I] [J] [K-1] используется только для расчета dist [i] [j] [k] , DIST [I] [J] останется DIST [I] [J] [K-1] в матрице до DIST [I] [J] [K] . Если I или j j k k , то применяется вышеуказанный случай.

Следовательно, порядок расчетов не имеет значения.

Теперь нам нужно показать, что dist [i] [j] = dist [j] [i] после всех этапов алгоритма.

Мы начинаем с симметричной сетки DIST [A] [B] = DIST [B] [A] , для всех A и B Отказ

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

Поэтому наше задание является и верным, и он будет поддерживать инвариантное значение dist [a] [b] = dist [b] [a] . Следовательно, dist [i] [j] = dist [j] [i] После всех этапов алгоритма

, следовательно, обе алгоритмы дают одинаковую, правильную, результат.

Скорость легче доказать. Внутренняя петля называется чуть более половины количества раз, когда она обычно называется, поэтому функция примерно вдвое больше. Просто сделали немного медленнее, потому что вы все еще назначаете одинаковое количество раз, но это не имеет значения, что и min () - это то, что занимает большую часть вашего времени.

Если вы видите что-то не так с моим доказательством, однако технические, не стесняйтесь указывать на это, и я попытаюсь его исправить.

Отредактируйте:

Вы можете ускорить и сохранять половину памяти, изменив петлю как таковой:

for (int k = 0; k < N; ++k) {
    for (int i = 0; i < k; ++i)
        for (int j = 0; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[i][k] + dist[j][k]);
    for (int i = k; i < N; ++i) {
        for (int j = 0; j < k; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[j][k]);
        for (int j = k; j <= i; ++j)
            dist[i][j] = min(dist[i][j], dist[k][i] + dist[k][j]);
    }
}

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

Благодаря Крису Элион для идеи.