I knew this could be done using Min Path finding algo. But what about DP for this problem , guys?
On Mon, Oct 31, 2011 at 3:49 AM, SAMM <somnath.nit...@gmail.com> wrote: > 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. > > -- 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.
