moving must be done in A* style On Mon, Jun 4, 2012 at 1:17 PM, atul anand <[email protected]> wrote:
> 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. > -- 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.
