Re: [algogeeks] Matrix Minimum Path Sum

[KK]

The problem u are referencing is different one.. here u can move in all 4 
directions!
On Wednesday, 6 June 2012 18:43:15 UTC+5:30, Dheeraj wrote:
>
> http://www.geeksforgeeks.org/archives/14943
>
> On Mon, Jun 4, 2012 at 7:57 PM, Decipher  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 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 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 
> wrote:
>
>> this recurrence wont work..ignore 
>>
>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand 
>> 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 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 algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to 
 algogeeks+unsubscribe@**googlegroups.com
 .
 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to algogeeks+unsubscribe@*
>> *googlegroups.com .
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
> googlegroups.com .
> 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 algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+unsubscribe@**
 googlegroups.com .
 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 view this discussion on the web visit 
>> https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ.
>>
>> To post t

Re: [algogeeks] Matrix Minimum Path Sum

[s yogeesh]

Guess the same Algo will do the job.
So time space and complexity will remain the same.
Correct me if 'm wrong.

-- 
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.

Re: [algogeeks] Matrix Minimum Path Sum

[Sourabh Singh]

 Basic Dijikstra problem . :-)

On Wed, Jun 6, 2012 at 6:13 AM, Dheeraj Jain  wrote:

> http://www.geeksforgeeks.org/archives/14943
>
>
> On Mon, Jun 4, 2012 at 7:57 PM, Decipher  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 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 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 
> wrote:
>
>> this recurrence wont work..ignore
>>
>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand 
>> 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 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 algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to
 algogeeks+unsubscribe@**googlegroups.com
 .
 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 algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to algogeeks+unsubscribe@*
>> *googlegroups.com .
>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
> googlegroups.com .
> 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 algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+unsubscribe@**
 googlegroups.com .
 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 view this discussion on the web visit
>> https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ.
>>
>> To post to this group, send email to algogeeks@googlegroups.com.
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com.
>> F

Re: [algogeeks] Matrix Minimum Path Sum

[Dheeraj Jain]

http://www.geeksforgeeks.org/archives/14943

On Mon, Jun 4, 2012 at 7:57 PM, Decipher  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 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 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 wrote:

> this recurrence wont work..ignore
>
> On Mon, Jun 4, 2012 at 8:55 AM, atul anand 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 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@
>>> **googlegroups.com .
>>> 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 algogeeks@googlegroups.com.
> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
> googlegroups.com .
> 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 algogeeks@googlegroups.com.
 To unsubscribe from this group, send email to algogeeks+unsubscribe@**
 googlegroups.com .
 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 algogeeks@googlegroups.com.
>>> To unsubscribe from this group, send email to algogeeks+unsubscribe@**
>>> googlegroups.com .
>>> 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 view this discussion on the web visit
> https://groups.google.com/d/msg/algogeeks/-/l9UCuzmoZRMJ.
>
> 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.
>

-- 
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 th

Re: [algogeeks] Matrix Minimum Path Sum

[Decipher]

@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 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 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 wrote:
>>>
 this recurrence wont work..ignore 

 On Mon, Jun 4, 2012 at 8:55 AM, atul anand 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 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 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.
>>
>
>
  -- 
 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.

>>>
>>>  -- 
>>> 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.
>>>
>>
>>  -- 
>> 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.
>>
>
>

-- 
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 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.

Re: [algogeeks] Matrix Minimum Path Sum

[Hassan Monfared]

moving must be done in A* style

On Mon, Jun 4, 2012 at 1:17 PM, atul anand  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 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 wrote:
>>
>>> this recurrence wont work..ignore
>>>
>>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand 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 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 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.
>


>>>  --
>>> 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.
>>>
>>
>>  --
>> 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.
>>
>
>  --
> 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.
>

-- 
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.

Re: [algogeeks] Matrix Minimum Path Sum

[atul anand]

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  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 wrote:
>
>> this recurrence wont work..ignore
>>
>> On Mon, Jun 4, 2012 at 8:55 AM, atul anand 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  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 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.

>>>
>>>
>>  --
>> 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.
>>
>
>  --
> 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.
>

-- 
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.

Re: [algogeeks] Matrix Minimum Path Sum

[Hassan Monfared]

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  wrote:

> this recurrence wont work..ignore
>
> On Mon, Jun 4, 2012 at 8:55 AM, atul anand 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  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 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.
>>>
>>
>>
>  --
> 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.
>

-- 
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.

Re: [algogeeks] Matrix Minimum Path Sum

[atul anand]

this recurrence wont work..ignore

On Mon, Jun 4, 2012 at 8:55 AM, atul anand  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  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 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.
>>
>
>

-- 
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.

Re: [algogeeks] Matrix Minimum Path Sum

[atul anand]

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  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 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.
>

-- 
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.