question archive Consider an undirected graph G = (V, E)
Consider an undirected graph G = (V, E)
Subject:Computer SciencePrice:2.89 Bought3
Consider an undirected graph G = (V, E). G has n nodes representing cities and m edges representing roads. Each road e ∈ E has an associate length le > 0. There is a proposal to add one new road to this network, and there is a list of E′ of pairs of cities between which the new road can be built. You are asked to determine the road e′ ∈ E′ whose addition to the existing network G would result in the maximum decrease in the driving distance between two fixed cities s and t in the network. Give an efficient algorithm for solving this problem.
Purchase A New Answer
Custom new solution created by our subject matter experts
GET A QUOTE
Answer Preview
A newly added edge e0 = (u, v) can only decrease the length of the shortest path from s to t if we follow e0. Thus, we would follow the paths s -> u -> v -> t. We can solve this problem by first using Dijkstra's algorithm to compute all shortest paths from s to any vertex, S[.] and to t from any vertex, T[.] (using GR if the graph is directed). For each possible new edge e0 = (u, v), the new shortest path length from s to t is S[u] + le0 + T[v]. We choose the edge e0 that minimizes this (Or none, if S[t] is never improved upon).
