Shortest path between 2 nodes using DP

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?

Hi, I found a solution with dp doing the next steps:

  • first, u have to identify the sub-problem ( state) , in this case is the short distance from 1 to node ith
  • the base case, in this problem is easy 'cause short[1]=0
  • and now the relations between the sub-problems, then it is the sum of the path to follow the next neighbor, but u only do it if the short[ith]+distance[ith,jth] is lower that short[jth], at the beginning you fill a vector short distance with INF, except with the base case

Now you can traverse the graph with dfs or bfs, i used bfs and as I said above you only add the queue the neighbor jth if the short[ith]+ distance[ith,jth] is lower that short[jth], 'cuase short[ith] is the optimal solutions currently found it. I’d hope this can be usefull for you.

rey abhijith

yo kireety

in what case path will not exist?

bump bump bump. As much as I can see Dijkstra’s algorithm is the best for this, but is this what I must use in this task given the hint? Also, the hint doesn’t really make any sense.