Question

Generalized shortest-paths problem.In Internet routing, there are delays on lines but also, more significantly, delays at routers. This motivates a generalized shortest-paths problem.

Suppose that in addition to having edge lengths $\left\{\left\{I_e:e\in E\right\}\right\}$ ,a graph also has vertex costs $\left\{c_V:v\in V\right\}$ . Now define the cost of a path to be the sum of its edge lengths, plusthe costs ofall vertices on the path (including the endpoints). Give an efficient algorithm for the followingproblem.

Input:A directed graph $\mathit{G}\mathbf{=}\left\{V,E\right\}$ positive edge lengths ${\mathbf{I}}_{\mathbf{e}}$ and positive vertex costs ${\mathit{c}}_{\mathbf{v}}$; a starting vertex $\mathit{s}\mathbf{\in }\mathit{v}$.

Output:An array $\mathit{c}\mathit{o}\mathit{s}\mathit{t}[.]$ such that for every vertex $\mathit{u}\mathbf{,}\mathit{c}\mathit{o}\mathit{s}\mathit{t}\left[u\right]$, is the least cost of any path from s to u (i.e., the cost of the cheapest path), under the defnition above.

Notice that $\mathit{c}\mathit{o}\mathit{s}\mathit{t}\left[s\right]\mathit{=}\mathit{c}$.

Short answer

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.

Bellman Ford algorithmis an application of single source shortest path, which is used for finding the shortest distance from one vertex to other vertices of a weighted directed graph. It is almost similar to Dijkstra's algorithm but Dijkstra's algorithm is works only for the graph with positive weight and Bellman Ford algorithm is works with graphs in which edges have negative weights in its graph.

Step-2: Reduction Method

The algorithm takes a directed graph $G=\left\{V,E\right\}$ with positive edge length ${\mathrm{I}}_{\mathrm{e}}$ and positive vertex costs $c_v$ as input, as well as an initial vertex to compute the cost of the cheap path.

The shortest-paths problem is generalised using the reduction method.Create a graph $G=\left\{V,E\right\}$ with the inputs . Because " G " only carries edge weights, the shortest path in $G$ from s to t is essentially the same as in G , with some minor differences. Bellman Ford algorithm is an application of single source shortest path, which is used for finding the shortest distance from one vertex to other vertices of a weighted directed graph.

It is almost similar to Dijkstra's algorithm but Dijkstra's algorithm is works only for the graph with positive weight and Bellman Ford algorithm is works with graphs in which edges have negative weights in its graph.

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 can be used to find the shortest path in G '.

• This is how the reducing process works:

Take all of the vertices in G and divide them into two vertices,$V_i$ and$v_0$

All edges entering$v_0$now enter$v_i$, whereas all edges leaving v now depart$v_0$.

Assume that the edge from$v_0$to$v_0$has a weight of$c\left(v\right)$.

• Consider one path in G , and notice how it may be transformed to an edge-weighted path of comparable weight in G' by changing the visit to vertex $V_0$, which includes the traversal of edge $\left(V_0,V_I\right)$.
• On the other hand, imagine a path in G : every extra edge visited in the operation $\left(v_i,v\right)$ corresponds to vertex $v_0$.
• To get a path in G with the same weight as the path in G' , swap these edges with the equivalent vertices.

The amount of time it will take to complete this decrease is role="math" localid="1658914597767" $O\left|V\right|+\left|E\right|$ .

Because graph has$O\left|V\right|+\left|E\right|$and $2\left|V\right|$ vertices, Dijkstra's algorithm takes time $O\left|V^2\right|$ and the overall running time is$O\left|V^2\right|$.