Dynamic programming and Dijkstra

782 views Asked by At

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?

0

There are 0 answers