Basic Dijikstra problem . :-) On Wed, Jun 6, 2012 at 6:13 AM, Dheeraj Jain <[email protected]> wrote:
> http://www.geeksforgeeks.org/archives/14943 > > > On Mon, Jun 4, 2012 at 7:57 PM, Decipher <[email protected]> wrote: > >> @Victor - Someone had asked this question from me !! He told me its from >> Project Euler Q-83. >> @Hassan - I think you are right. This question can be solved by >> Dijikstra's algo, if we consider the matrix elements as weights. >> >> >> On Monday, 4 June 2012 16:28:31 UTC+5:30, Hassan Monfared wrote: >>> >>> 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<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 >>>>>>>> algogeeks+unsubscribe@**googlegroups.com<algogeeks%[email protected]> >>>>>>>> . >>>>>>>> For more options, visit this group at http://groups.google.com/** >>>>>>>> group/algogeeks?hl=en<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 algogeeks+unsubscribe@* >>>>>> *googlegroups.com <algogeeks%[email protected]>. >>>>>> For more options, visit this group at http://groups.google.com/** >>>>>> group/algogeeks?hl=en<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 algogeeks+unsubscribe@** >>>>> googlegroups.com <algogeeks%[email protected]>. >>>>> For more options, visit this group at http://groups.google.com/** >>>>> group/algogeeks?hl=en <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 algogeeks+unsubscribe@** >>>> googlegroups.com <algogeeks%[email protected]>. >>>> For more options, visit this group at http://groups.google.com/** >>>> group/algogeeks?hl=en <http://groups.google.com/group/algogeeks?hl=en>. >>>> >>> >>> -- >> 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/-/l9UCuzmoZRMJ. >> >> 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.
