Search code examples
algorithmmathdata-structuresgraphgraph-algorithm

very hard and elegant question on shortest path

Given a weighed, connected and directed graph G=(V,E) with n vertexes and m edges, and given a pre-calculated shortest path distance's matrix S where S is n*n S(i,j) denotes the weight of shortest path from vertex i to vertex j.

we know just weight of one edge (u, v) is changed (increased or decreased).

for two specific vertex s and t we want to update the shortest path length between these two vertex.

This can be done in O(1).

How is this possible? what is the trick of this answer?

Solution

  • 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):

    https://i.imgur.com/94LjDYt.png

    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.