題組內容

2. A weighted graph G=(V, E) is an undirected graph with nonnegative weight assigned to each edge in E. The length of a path in G is the sum of edge weights of the edges in the path. A path P from vertex u to vertex v is said to be shortest if the length of P is smallest for all paths from vertex u to vertex v.

(A)(12%) For a weighted graph G-(V, E) and two vertices x, y in Y, give an efficient algorithn to find a shortest path from x to y. Analyses the time complexity of the algorithm.