Justify this by induction on the length of a shortest path from the start vertex.