i dont think so dijistra will worh here..bcozz we cannot move diagonally ...but according to matrix this path can be considered.
On Mon, Jun 4, 2012 at 1:39 PM, Hassan Monfared <[email protected]> wrote: > for non-negative values Dijkstra will solve the problem in ( O(N^2) ) > and Floyd-Warshal is the solution for negative cells. ( O(N^3) ) > > > > On Mon, Jun 4, 2012 at 11:20 AM, atul anand <[email protected]>wrote: > >> this recurrence wont work..ignore >> >> On Mon, Jun 4, 2012 at 8:55 AM, atul anand <[email protected]>wrote: >> >>> find cumulative sum row[0] >>> find cumulative sum of col[0] >>> >>> after this following recurrence will solve the problem. >>> >>> start from mat[1][1] >>> >>> mat[i][j]=mat[i][j]+min( mat[i][j-1] , mat[i-1][j] ) >>> >>> >>> On Sun, Jun 3, 2012 at 7:30 PM, Decipher <[email protected]> wrote: >>> >>>> Q) In the 5 by 5 matrix below, the minimal path sum from the top left >>>> to the bottom right, by moving left, right, up, and down, is indicated in >>>> bold red and is equal to 2297. >>>> >>>> >>>> *131* >>>> >>>> 673 >>>> >>>> *234* >>>> >>>> *103* >>>> >>>> *18* >>>> >>>> *201* >>>> >>>> *96* >>>> >>>> *342* >>>> >>>> 965 >>>> >>>> *150* >>>> >>>> 630 >>>> >>>> 803 >>>> >>>> 746 >>>> >>>> *422* >>>> >>>> *111* >>>> >>>> 537 >>>> >>>> 699 >>>> >>>> 497 >>>> >>>> *121* >>>> >>>> 956 >>>> >>>> 805 >>>> >>>> 732 >>>> >>>> 524 >>>> >>>> *37* >>>> >>>> *331* >>>> >>>> >>>> >>>> Write an algorithm to find the same. Also, write an algorithm if the >>>> same matrix contains negative numbers (maybe negative cycle) and compare >>>> the space and time complexity of both. >>>> >>>> -- >>>> You received this message because you are subscribed to the Google >>>> Groups "Algorithm Geeks" group. >>>> To view this discussion on the web visit >>>> https://groups.google.com/d/msg/algogeeks/-/3JeyGNqWbs8J. >>>> To post to this group, send email to [email protected]. >>>> To unsubscribe from this group, send email to >>>> [email protected]. >>>> For more options, visit this group at >>>> http://groups.google.com/group/algogeeks?hl=en. >>>> >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
