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 element 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

changes requared:
i) Cost of starting node should be considered 1 and not zero

algorithm:
  
dist[s] <- 1 //s is the start node
for all v V-{s}
      do dist[v] <- Infinite //travelling time to other node is infinite
S<-Empty set   // S, is the set of visited vertices is initially empty
Q<-V //Q is the set of not visited nodes
while Q is not empty
do u <— mindistance(Q,dist) //mindistance returns the vertex from Q with minimum distance
    S<—S U {u}  
    for all v that are neighbour of u
   do if dist[v] > dist[u] * w(u, v) //if new shortest path found
             then d[v] <—d[u] * w(u, v) //set new value of shortest path
end while
return dist

I hope you like it!

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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