試題詳解

26. Let G =(V, E) be an undirected connected graph, where each edge e has a given length I(e)＞ 0. Let s be a fixed vertex of this graph and let δ(v) be the length of a shortest path from s tov. Which one of the following statements is not correct?
(A) For each vertex v ≠s, there is an incident edge e=(u,v) such that  δ(V)=δ(น)+l(e).
(B) For each vertex v≠s, choose one incident edge e=(u,v) such that δ(V)=δ(น)+l(e),the collection of these edges forms a spanning tree of G.
(C) For each vertex v≠s, choose one incident edge e=(u,y) such that δ(V)=δ(น)+l(e),the collection of these edges forms a minimum weight spanning tree of G.
(D) Bellman-Ford algorithm can find a shortest path from s to v in this case.
(E) Dijkstra's algorithm can find a shortest path from s to v in this case.