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.
