Hi guys, I’m trying to solve this problem :
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.
From TopCoder dp content. The first thing that come to my mind is find all the paths to node N using BFS or DFS. Is there a better way using DP?