CODEWITHSUNDEEP
dynamic-programmingshortest-pathgreedy
Nikhil Verma
Nikhil Verma

Reputation: 1730

shortest path in graph

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 found this question on topcoder, I think Dijkstra's algo should be used, but the post is regarding Dynamic programming and Dijkstra is a greedy algo.

Can anyone tell me the best way to solve this problem.

Thanks

Upvotes: 1

Views: 404

Answers (1)

Michelle Lin
Michelle Lin

Reputation: 11

Yes, although the question is categorized under dynamic programming, you can use EITHER dynamic programming or Dijkstra's Single Source Shortest path greedy algorithm.

Does the greedy algorithm work? Always think through these two steps:

  1. Ask yourself if your problem has the optimal substructure property. For example, if the shortest path from vertex A to G contains B, then the path from A to B must also be the shortest. This sub-structure, path AB, is optimal as it itself is also the shortest path. So yes, the problem you described as the optimal substructure property.

  2. Does the algorithm have a greedy choice property? Is the first step part of the optimal solution, is the second and so on and so on. Yes, Dijkstra's algorithm does have the greedy choice property because each vertex uses the local information of all vertex pointing towards it to "pick" the smallest value. The algorithm only moves forwards and never moves back and only changes the min value for each vertex A if and only if the information is new (found a new vertex B of a shorter distance that also points to A) and fulfills some condition.

Here's an overview of Dijkstra's algo:

Each vertex X will have 2 components: current shortest path & the prev vertex Y associated with it that points at X.

  1. set all vertex current shortest path to infinity
  2. set a starting point - which would be 1 in this case
  3. for each of vertex X's neighbors vertex Y, Y's current shortest path is the minimum of X's shortest path + the distance between the two AND Y's current shortest path. Update the prev vertex if Y's current shortest path is changed.
  4. do the same for all of Y's neighbors and so on until there are no more vertexes left.

In your case however, you don't need to record the prev index as all you have to output is the length or if it's not possible.

At the end, you should have some sort of table/list based on your choice of data structure such that if you look up a certain vertex N, it tells you the length from vertex 1. If the length from vertex 1 is infinity then it is not possible. Of course, you could also do some book keeping such a bool value associated with each vertex.

Keep in mind that Dijkstra's will have a O(V^2) running time. Dynamic programming may generate a faster running time.

Upvotes: 0

Related Questions