You certainly can for decreases. I assume S
will always refer to the old distances. Let l
be the new distance between (u, v)
. Check if
S(s, u) + l + S(v, t) < S(s, t)
if yes then the left hand side is the new optimal distance between s
and t
.
Increases are impossible. Consider the following graph (edges in red have zero weight):
Suppose m
is the minimum weight edge here, except for (u, v)
which used to be lower. Now we update (u, v)
to some weight l > m
. This means we must find m
to find the new optimum length.
Suppose we could do this in O(1) time. Then it means we could find the minimum of any array in O(1) time by feeding it into this algorithm after adding (u, v)
with weight -BIGNUMBER
and then 'updating' it to BIGNUMBER
(we can lazily construct the distance matrix because all distances are either 0
, inf
or just the edge weights). That is clearly not possible, thus we can't solve this problem in O(1) either.
与恶龙缠斗过久,自身亦成为恶龙;凝视深渊过久,深渊将回以凝视…