As in breadth-first search,we shall be interested in the predecessor subgraph G=(Vz,Ex)induced by the n values.Here again,we define the vertex set V to be the set of vertices of G with non-NIL predecessors, plus the source s: Vx={v∈V:u.π≠NIL}U{s}. The directed edge set E is the set of edges induced by the values for vertices in V: Em={(v.π，v)∈E:v∈Vx-{s}. A shortest-paths tree rooted at s is a directed subgraph G'=(V',E). where v'V and E'C E,such that 1.V'is the set of vertices reachable froms in G, 2.G'forms a rooted tree with root s,and 3.for all vV,the unique simple path from s to v in G'is a shortest path froms to v in G. Predecessor-subgraph property (Lemma 24.17) Once v.d=8(s.v)for all vV.the predecessor subgraph is a shortest-paths tree rooted at s