(Label Correcting for Acyclic Graphs) Consider the problem of finding shortest paths from the origin node 1 to all destinations, and assume that the graph does not contain any forward cycles. Let Tk be the set of nodes i such that every path from 1 to i has k arcs or more, and there exists a path from 1 to i with exactly k arcs. For each i, if i ∈ Tk define INDEX(i) = k. Consider a label setting method that selects a node i from the candidate list that has minimum INDEX(i).
(a) Show that the method terminates and that each node visits the candidate list at most once.
(b) Show that the sets Tk can be constructed in O(A) time, and that the running time of the algorithm is also O(A).