CODEWITHSUNDEEP
algorithmmathdata-structuresgraphgraph-algorithm
user5927605
user5927605

Reputation:

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?

Upvotes: 6

Views: 331

Answers (1)

orlp
orlp

Reputation: 117641

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.

Upvotes: 2

Related Questions