You are given a black box Dijkstra’s implementation You are given a black box Di

Question

You are given a black box Dijkstra’s implementation

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

computing shortest path :

n<--- rows[W]

D(0)<--W

for k<---1 to n

do for i<-- 1 to n

                    do for j <--- 1 to n

                     dij(k) <--- min (dij(k-1), dik(k-1) + dkj(k-1))

return D(n)

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

---

---

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