CODEWITHSUNDEEP
algorithmshortest-path
Suresh Iyengar
Suresh Iyengar

Reputation: 59

Weighted graph and all pairs path

Am trying to solve a question at this link:

https://www.chegg.com/homework-help/questions-and-answers/consider-weighted-directed-graph-g-n-vertices-e-edges-weights-integers-suppose-g-contains--q12054851

(this is not a homework question)

Consider a weighted directed graph G with n vertices and e edges, and the weights are integers. Suppose that G contains no negative cycles, and for every pair of vertices u and v in G, the distance from u to v falls in the range [-2d, 2d] for some positive integer d. We are going to fix a particular edge (x,y) in G, and consider what happens to the distances in G as we change the weight associated with that edge (and leave all other edge weights fixed).

Design an algorithm that takes G as input, as well as a specified edge (x,y) in G. The output of the algorithm should be an integral range of values that the weight of this edge (x,y) could take such that all of the distances in G would remain the same. Note that this range will be non-empty, as it must include the original weight of the edge (x,y). Also note that infinity may occur as an endpoint of your range (i.e. the range may not be finite). For this, you may return “∞” as an endpoint. The running time of your algorithm must be polynomial in n,e, and d (so your running time should not have any of these parameters appearing as exponents). Prove why the algorithm is correct.

I have been thinking on the following lines: Since distances are in a range, weights should also be in a range. One option is we run Djkstra's multiple times. How do we optimize this?

Upvotes: 1

Views: 185

Answers (1)

HenryLee
HenryLee

Reputation: 406

Yes, you can run Dijkstra n times. Alternatively you can run Floyd-Warshall, which is designed for these problems. Overall, they have similar complexity bounds.

Upvotes: 1

Related Questions