This can be done using the Dijkstra's algorithm , Start frm the source frm the Destination (In this example from (2 2)) . You need to consider the index of the array as the the vertices and the weigjht as the the value for the movement from the present vertex to it's connecting neighbour ..
On 10/31/11, mohit verma <mohit89m...@gmail.com> wrote: > Given a matrix you have to find the shortest path from one point to another > within the matrix. The cost of path is all the matrix entries on the way. > You can move in any direction (up, down, left, right, diagonally) > > e.g. > > 5 9 10 1 > 3 7 4 4 > 8 2 1 9 > > So shortest path from (0,0) to (2,2) is (0,0)--(1,1)---(2,2). Path cost - > 5+3+2+1=11 > > I dont think some DP solution exist for this problem.Can it be? > > > -- > Mohit > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- Somnath Singh -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
