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.