Variations of Dijkstra’s Algorithm . [15 marks] Explain what adjustments if any

Question

Variations of Dijkstra’s Algorithm. [15 marks] Explain what adjustments if any need to be made in Dijkstras algorithm and/or in an underlying graph to solve the following problems.

(a) Solve the single-source shortest-paths problem for directed weighted graphs.

(b) Find a shortest path between two given vertices of a weighted graph or digraph. (This variation is called the single-pair shortest-path problem.)

(c) Find the shortest paths to a given vertex from each other vertex of a weighted graph or digraph. (This variation is called the single-destination shortest-paths problem.)

Explanation / Answer

a. It will suffice to take into account edge directions in processing adjacent vertices.

b. Start the algorithm at one of the given vertices and stop it as soon as the other vertex is added to the tree.

c. If the given graph is undirected, solve the single-source problem with the destination vertex as the source and reverse all the paths obtained in the solution. If the given graph is directed, reverse all its edges first, solve the single-source problem for the new digraph with the destination vertex as the source, and reverse the direction of all the paths obtained in the solution. d. Create a new graph by replacing every vertex v with two vertices v and v connected by an edge whose weight is equal to the given weight of vertex v. All the edges entering and leaving v in the original graph will enter v and leave v in the new graph, respectively. Assign the weight of 0 to each original edge. Applying Dijkstra’s algorithm to the new graph will solve the problem.

Related Questions

Navigate

• Browse (All)
• Browse V
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.