Hi Mohit, Bellman-Ford algorithm is a dynamic programming algorithm but u need it only if dijkstra's SP wont solve the problem... and Dijkstra's algo works only for +ve weights. So if u r sure that there maybe negative weights then you will need to use bellmann ford which is a DP algo.
On Mon, Oct 31, 2011 at 7:40 AM, mohit verma <mohit89m...@gmail.com> wrote: > 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. > -- Vandana Bachani Graduate Student, MSCE Computer Science & Engineering Department Texas A&M University, College Station -- 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.
