Assume there is an algorithm that solves the single-source shortest path problem in O(n+m) time for directed graphs with
Posted: Mon Jul 11, 2022 9:56 am
Assume there is an algorithm that solves the single-sourceshortest path problem in O(n+m) time for directed graphs with nvertices, m edges, and non-negative integer edge weights. Let'scall this algorithm SHORT. Using SHORT, design a O(n+m) algorithmfor an adjacency list representation of an unweighted directedgraph G. Given two designated vertices s, t ∈ V and a subset B ⊆ Vof the vertices are labeled as “purple” vertices. Find a path froms to t that visits as few purple vertices as possible