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

Немного подумав, я пришел к следующему:

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

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

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

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

Определим 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 оптимизированного алгоритма, поэтому он по-прежнему правильный и, вероятно, получит ту же скорость, но использует половину памяти.

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

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

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