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:54 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) algorithm for an adjacency listrepresentation of an unweighted directed graph G. Given twodesignated vertices s, t ∈ V and a subset B ⊆ V of the vertices arelabeled as “purple” vertices. Find a path from s to t that visitsas few purple vertices as possible
Using SHORT, design a O(n+m) algorithm for an adjacency listrepresentation of an unweighted directed graph G. Given twodesignated vertices s, t ∈ V and a subset B ⊆ V of the vertices arelabeled as “purple” vertices. Find a path from s to t that visitsas few purple vertices as possible