Оптимизировать матрицу Флойда-Уорсхолла для симметричной матрицы смежности

Question

Существует ли оптимизация, которая снижает постоянный коэффициент времени выполнения Floyd-Warshall, если вы гарантированно получаете симметричную матрицу смежности?

Answer 1

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

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]);

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

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

Входная матрица имеет вид симметричный.Теперь остальная часть доказательства использует модифицированное доказательство Флойда-Варшалла, чтобы показать, что порядок вычислений в 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 равно 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]);
    }
}

Это просто разделяет приведенные выше циклы оптимизированного алгоритма for, поэтому он по-прежнему корректен и, скорее всего, получит ту же скорость, но использует половину памяти.

Спасибо Крису Элиону за идею.

Answer 2

(Используя обозначение в псевдокоде в статье Википедии) Я считаю (но не проверял), что если матрица edgeCost симметрична, то матрица path также будет симметричной после каждой итерации.Таким образом, вам нужно обновлять только половину записей на каждой итерации.

На более низком уровне вам нужно сохранить только половину матрицы (поскольку d (i, j) = d (j, i)), так что вы можете уменьшить объем используемой памяти и, надеюсь, уменьшить количество промахов кэша, поскольку вы будете обращаться к одним и тем же данным несколько раз.