I'm reading the following problem statement meant to be solved with dynamic programming:
Given an undirected graph G having N
(1<N<=1000)
vertices and positive weights. Find the shortest path from vertex 1 to vertex N, or state that such path doesn’t exist.Hint: At each step, among the vertices which weren’t yet checked and for which a path from vertex 1 was found, take the one which has the shortest path, from vertex 1 to it, yet found.
I believe the algorithm should be something like
S = starting point
N = ending point
initialize all distances from S to +infinity
unexplored_vertices[] = [all vertex adjacent to S]
for each v in unexplored_vertices[]
calculate new_distance from S to v
if new_distance is better than the former then
store new_distance
closest_to_v = find(unexplored_vertices[], closest_to_S)
unexplored_vertices[].add_front(closest_to_v)
return distance from S for N
Anyway this is very similar to how Dijkstra's algorithm works for shortest paths.
My question is: am I getting the problem statement wrong or is the statement really asking (along with the hint) for Dijkstra's shortest path algorithm?