Sharp distance labels. The generic label-correcting algorithm maintains a predecessor graph at every step. We say that a distance label d(i) is sharp if it equals the length of the unique path from node s to node i in the predecessor graph. We refer to an algorithm as sharp if every node examined by the algorithm has a sharp distance label. (A sharp algorithm might have nodes with nonsharp distances, but the algorithm never examines them.)
(a) Show by an example that the FIFO implementation of the generic label-correcting algorithm is not a sharp algorithm.
(b) Show that the dequeue implementation of the generic label correcting is a sharp algorithm. (Hint: Perform induction on the number of nodes the algorithm examines. Use the fact that the distance label of a node becomes nonsharp only when the distance label of one of its ancestors in the predecessor graph decreases.)