thnx all On Mon, Oct 31, 2011 at 10:13 PM, Vandana Bachani <vandana....@gmail.com>wrote:
> 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. > -- 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.
