An algorithm problem Let G = (V, E) be a directed weighted graph of the US highw

Question

An algorithm problem

Let G = (V, E) be a directed weighted graph of the US highway system, with edge weights being distances between dierent cities/intersections. Boulder and Denver are two vertices of G, and k > 0 is a given integer. Assume that you will stop at every city/intersection you pass by. Design an algorithm to nd the shortest path from Boulder to Denver that contains exactly k stops (excluding Boulder and Denver), and prove its correctness. Notice that a k-stop path from Boulder to Denver may not exist. So, your algorithm should also take care of such a possibility.

Explanation / Answer

ALGORITHM

compute core {v V : deg(v) > n" /4}

for each v core do

   run breadth-first search from v in G

       for each node u *= v, store d(u, v) and let FirstNodeu(v) be the penultimum node on the      shortest path; update L(u) if v is nearest landmark

end for

    for each u V do

    compute and store Bcore(u) (including distances)

    for each v Bcore(u) let FirstNodeu(v) be the first node on the shortest path to v.

end for

Related Questions

Navigate

• Browse (All)
• Browse A
• Subjects

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