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?
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.
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.
in what case path will not exist?