Chapter 4: Q20E (page 137)

There is a network of roads G=(V,E) connecting a set of cities . Each road in E has an associated length $I_{e}$ . There is a proposal to add one new road to this network, and there is a list E' of pairs of cities between which the new road can be built. Each such potential road localid="1659075853079" $e' \in E'$ has an associated length. As a designer for the public works department you are asked to determine the road localid="1659075866764" $e' \in 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.

Short Answer

Expert verified

answer is not available.

Step by step solution

Step-1: Shortest Path Problem

The shortest path issue in graph theory is the task of finding a path between two vertex (or nodes) in a graph that minimizes the total of the weights of its constituent edges. For multiplicative weights, the generalised shortest path issue can be resolved quickly. The solution is to invert Dijkstra's algorithm.

Dijkstra algorithm is an application of single source shortest path.Dijkstra’s algorithm also known as SPF algorithm and is an algorithm for finding the shortest paths between the vertices in a graph. It returns a search tree for all the paths the given node can take. An acyclic graph is a directed graph that has no cycles. Its operation is performed in the minheap.

Dijkstra’s algorithm is a single-source shortest path problem. It is used in both directed and undirected graph with non negative weight.

Step-2: Algorithm for determining shortest path.

Take a look at the graph G=(V,E) and the new edges E' . Now choose an edge(road) $e' \in E'$ .

Assume that $e' = (x, y)$ and $e' = I_{e}$ , are both equal in length. The shortest distance from s to t is then calculated by $d_{s} (x) + I_{e} + d_{t} (y)$ .

Dijkstra's algorithm can be used to find the shortest path distances. To find the shortest path distance from s to x , run the Dijkstra's algorithm once from . Run the Dijkstra's method again from t to get the shortest path distance between v and t .

And the shortest path issue in graph theory is the task of finding a path between two vertex (or nodes) in a graph that minimizes the total of the weights of its constituent edges. For multiplicative weights, the generalised shortest path issue can be resolved quickly. The solution is to invert Dijkstra's algorithm.

Assume that when Dijkstra's algorithm is run from vertex, it finds the shortest distance betweenand all vertices, which is represented by $d i s (s, u)$ , u can represent any vertex in the graph.

Dijkstra’salgorithm is a single-source shortest path problem. It is used in both directed and undirected graph with non negative weight.

Next, calculate the length of the shortest path from s to t through each edge $e' \in E$ , and choose the best edge that delivers the least distance between s s and t .

From s to any node x , use Dijkstra, and from to any node y , use Dijkstra.
The shortest distances between $s (d_{s} (x))$ and $t (d_{t} (y))$ will be obtained as a result of this.
Then locate the edge that minimizes $d_{s} (x) + I_{e} + d_{t} (y)$ by iterating over all. Dijkstra plus $e = (x, y) E' (y)$ ,which is $o |E| \log V + |E'|$ is the total running time $O (|F'|)$ .