You are given a black box Dijkstra\'s implementation, D, that takes as input a d

Question

You are given a black box Dijkstra's implementation, D, that takes as input a directed graph G = (V, E), vertices u, v elementof V, and weighing function W: E rightarrow R^+ and computes the shortest path between the vertices u, v using the costs returned by W. It is common to want to compute the shortest path of a graph where the path-cost is the product of all the edge-costs in the path instead of the sum of the edge costs. However, since we already have an implementation of Dijkstra 's using sum costs, we do not wish to duplicate work. Give an algorithm P that on input P(G, W, u, v) with W: E rightarrow Z^+, computes the shortest product path using D to do most of the work.

Explanation / Answer

Step 1: Create a set setOpt (shortest path tree set) that keeps track of vertices included in shortest path tree, i.e., whose minimum distance from the source is calculated and finalized. Initially, this set is empty.

Step 2: Assign a distance value to all vertices in the input graph. Initialize all distance values as INFINITE. Assign a distance 0 to the source node so that it will be picked first.

Step 3: While setOpt doesn’t include all vertices

(i) Pick a vertex u which is not there in setOpt and has minimum distance value.

(ii) Include u to setOpt

   (iii) Update distance value of all adjacent vertices of u. To update the distance values, iterate through all adjacent vertices. For every adjacent vertex v, if the product of distance value of u (from source) and weight of edge u-v, is less than the distance value of v, then update the distance value of v.

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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