Блог

Учитывая взвешенный, связанный и ориентированный граф G=(V,E) с n вершинами и m ребрами и учитывая предварительно рассчитанную матрицу расстояния кратчайшего пути S , где S n*n S(i,j) обозначает вес кратчайшего пути от вершины i к вершине j .

мы знаем (u, v) , что изменяется (увеличивается или уменьшается) только вес одного ребра.

для двух конкретных вершин s , и t мы хотим обновить длину кратчайшего пути между этими двумя вершинами.

Это можно сделать в O(1).

Как это возможно? в чем подвох этого ответа?

Вы, конечно, можете уменьшить. Я предполагаю S , что всегда будет ссылаться на старые расстояния. Пусть l будет новое расстояние между (u, v) . Проверьте, если

 S(s, u)   l   S(v, t) < S(s, t)
 

если да, то левая сторона — это новое оптимальное расстояние между s и t .

Увеличение невозможно. Рассмотрим следующий график (ребра в красном имеют нулевой вес):

Предположим m , что здесь минимальное значение веса, за исключением (u, v) того, которое раньше было ниже. Теперь мы обновляем (u, v) до некоторого веса l > m . Это означает, что мы должны найти m , чтобы найти новую оптимальную длину.

Предположим, мы могли бы сделать это за O (1) время. Тогда это означает, что мы могли бы найти минимум любого массива за O (1) время, загрузив его в этот алгоритм после добавления (u, v) веса -BIGNUMBER , а затем «обновив» его до BIGNUMBER (мы можем лениво построить матрицу расстояний, потому что все расстояния либо 0 равны, inf либо просто весам ребер). Это явно невозможно, поэтому мы также не можем решить эту проблему в O (1) .