• Post Reply Bookmark Topic Watch Topic
  • New Topic

Need help for finding shortest path in a matrix.  RSS feed

 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I tried it myself but with no success.

for example if I have:

3 13 15
40 51 52
28 10 53

I must have this rule : the next cell I go to is greater than the previous one. and second rule, must use static recursive function.
we can go from : 3->13->15->52->53 , so totall path is : 5.

this is what I have tried for 3 hours. I will really be glad if someone can help me with this.



I know I will need maybe to change it to :

 
Knute Snortum
Sheriff
Posts: 4279
127
Chrome Eclipse IDE Java Postgres Database VI Editor
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think you need to start over. First, you can't assume you know how long the path will be. Writing return F()+F()+F()... won't work if you have a 4 X 4 grid or bigger. Instead, try breaking the problem into one-step pieces. I'd start with, "If I am at r1c1, which path is longer? r2c1 or r1c2?" You can't answer this without knowing which path is longer in the next step.
Try writing out the steps before you start coding.
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Knute Snortum wrote:I think you need to start over. First, you can't assume you know how long the path will be. Writing return F()+F()+F()... won't work if you have a 4 X 4 grid or bigger. Instead, try breaking the problem into one-step pieces. I'd start with, "If I am at r1c1, which path is longer? r2c1 or r1c2?" You can't answer this without knowing which path is longer in the next step.
Try writing out the steps before you start coding.


I understand.
I manage it through. my problem now is how to save the value of the length of the paths ?

if I have 3->13->15->52->53 now the length of the path is 5 and I need to keep it and compare it to other paths length .

if I had a different array (2X2) like the one above I could have longer path :
if I have 3->13->51>62->63->70->80 the length is 7 and I need to keep the value and compare it to 5 (length of previous path)

how can I do this ?

I will be glad if someone can really guide me here since I already on this 6 hours and it's really hard for me to acomplish this .

thanks.
 
Tyson Lindner
Ranch Hand
Posts: 211
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This is more of an intermediate level java problem so don't be dismayed if its taking you longer than a few hours. A variation of this problem (percolation) was one of the first assignments for an intro to algorithms course I took which is at least a step ahead of beginner programming.

Basically the idea here is that you are given an initial matrix and starting location so to find the shortest path you would then check for the shortest path from all of the legal squares (adjacent ones with higher numbers) and then add the shortest to the length of your path so far. So to do this you only really need one method, which passes the matrix along with the starting location and just returns an int. The matrix stays the same all the time but the starting location changes. You also need to the method to check for situations where there is no legal path and return an appropriate value (I recommend -1), and also of course check for an end condition where you are only 1 away from your goal and no longer need to use recursion.
 
Tyson Lindner
Ranch Hand
Posts: 211
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Dan D'amico wrote:
I manage it through. my problem now is how to save the value of the length of the paths ?

if I have 3->13->15->52->53 now the length of the path is 5 and I need to keep it and compare it to other paths length .


You don't get all the possible paths in the matrix in a list or something and then start comparing them, you merely get each subpath from each starting location and compare those. For example, starting with 3, we're only comparing F(1,0) and F(0,1) which is 13 and 40 respectively. Whichever is shorter we add one (since we've taken one step) and then just return that value. So then we do the same thing for the (1,0) in which the legal squares are (2,0) and (1,1) (15 and 40 respectively) and for the (0,1) spot where there is only legal square which is (1,1)(51). Eventually you will be adjacent to your goal in which case there is no more recursion and you can just return 1, or there will be no legal squares in which you should probably return -1.
 
Dan D'amico
Ranch Hand
Posts: 94
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I have a test in 3 days.
if someone here can sit with me for an hour via skype I will pay via paypal, let me know.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!