Simple shortest path problem in matrix.

Hi,

I have a very simple problem.

I have a matrix which elements can have values 1 or 0 only. I need to find the shortest path from the first to last row.

Any movement across the element with the value 1 is free.

Any vertical or horizontal movement is worth 1 and any diagonal movement is worth sqrt(2) when the movement is across the element with the value 0.

I would very much appreciate any help with this.

Regards!

[Azzi Abdelmalek]

What is the size of your matrix?

[Walter Roberson]

To confirm:

Moving from 1 to 1 is free, whether the movement is horizontal, vertical or diagonal?

Moving from 0 to 0 costs 1 when the movement is horizontal or vertical, and sqrt(2) when the movement is diagonal?

How about the costs to move from 0 to 1, or from 1 to 0, in the various directions?

[Seeker]

Matrix shouldn't be too large, not more than 500x500. The point is to input any matrix.

Moving from 1 to 1 is free, whether the movement is horizontal, vertical or diagonal? Yes

Moving from 0 to 0 costs 1 when the movement is horizontal or vertical, and sqrt(2) when the movement is diagonal? Yes

How about the costs to move from 0 to 1, or from 1 to 0, in the various directions?

Moving from 0 to 1 is free in any direction. Moving from 1 to 0 is 1 (horizontal or vertical) and sqrt(2) (diagonal).

[Seeker]

I've tried similar to this http://blogs.mathworks.com/steve/2011/12/02/exploring-shortest-paths-part-3/, but this is only with two clusters connected (in my case clusters of 1s). What if I have random number of these clusters all over the matrix and I need to connect the first row with the last row.

I hope the question is clearer now.

[Image Analyst]

And not a single one of the 66 submissions in the File Exchange could be adapted to your problem? Surely at least one of them could be a good starting point.

[Seeker]

I have looked through them. I have matrix, not graph. Only somehow applicable function is 'Finding optimal path on a terrain' but mine is not 3D problem.

[Azzi Abdelmalek]

You said from the first row to the last row. Which value from the first row? Also you have to specify what do you mean by diagonal: a(1,1) to a(2,3) is it a diagonal?

[Seeker]

Any element on the first row to any element on the last row, equivalent to consider that all the elements in the first row are 1 and all elements in the last row are 1.

Transition (1,1) to (2,3) is not allowed. You can only move as a king in chess where the weights are as described above.

[Azzi Abdelmalek]

Ok. I understand, but this is not a simple problem like you said!

[Seeker]

Yes, I realized that after spending the whole day trying to get a right approach.

I was hoping I would be able to use this http://blogs.mathworks.com/steve/2011/11/26/exploring-shortest-paths-part-2/.

Pretty elegant solution, but unfortunately it seems it isn't applicable to my problem.

Thank you anyway and any further suggestion is welcomed.

Answer 1

[Image Analyst]

Try the File Exchange first: http://www.mathworks.com/matlabcentral/fileexchange/index?utf8=%E2%9C%93&term=shortest+path

[Seeker]

I did. But everything there looks like a overkill. Mine is much simpler problem and those functions are not really applicable.

Thank you, anyway.

Answer 2

[Alex Foreever]

This is a wild suggestion.

consider the matrix as a tree such that 1)each adjacent elements with values 0 are nodes. 2)Distance between nodes representing vertically and horizontally adjacent elements are 1. 3)Similarly put distance between diagonally adjacent nodes as root(2).

Then perform a shortest distance algorithm on it.

[Seeker]

Thanks for the suggestion. :)

[Image Analyst]

Alex, that's what many of the files in the File Exchange that I suggested do, such as this one: http://www.mathworks.com/matlabcentral/fileexchange/26723-demonstration-of-astar-a, which uses the A* algorithm, my favorite. You have a matrix (or an image) but it can of course be considered as a tree. For some reason, Seeker does not see how they apply to his situation.

[Seeker]

I appreciate your help. But there are a few things you should take into account.

First, I am a novice in Matlab and to significantly modify someone's code is very challenging for me. The codes I read (and I read quite a few are quite different from what I need).

I already posted tutorial on the shortest path between two objects, but I couldn't generalized that on my problem.

How should I generate cost_matrix (even if I understand and apply Dijstra algorithm). I might have 200 nodes, it is just impossible to do it manually.

I don't know why do you insist on that I should go through other codes (66 of them) and then it might be something in there I would be able to use...

If someone asks my help with a problem (that might be quite simple), in something I understand quite well, I wouldn't just quote a book (with 200 pages) and somewhere in there it might have some similarities to the problem.

Do you understand that for me it would take at least 2 weeks to try all of that and I am pretty sure it won't help more then using google. I understand this forum as something that might be more useful.

All the best.

[Walter Roberson]

First, I am a novice in Matlab

What computer language are you more advanced in? Chances are you could write the program in that language and then transcribe it to MATLAB.

[Image Analyst]

Well what you're asking for is not trivial. It's not something one of us could bang out in five minutes and give to you. It's not going to be some short program of 20 or 30 lines. It would take a lot longer than 5 minutes, hence my suggestion to look at people who have already spent that time developing and debugging their program.

Answer 3

[Walter Roberson]

If your image has any two adjacent 0 pixels adjacent to the shortest path that involves only 1's, then there is no solution to the problem, as the path can move back and forth between the two 0's indefinitely without increasing the cost.

[Seeker]

Hm, good point. That's why I need the advice on this.

I was trying to solve it today using Steve's tutorial ( http://blogs.mathworks.com/steve/2011/11/26/exploring-shortest-paths-part-2/).

Here is the example what I need. As you can see it doesn't work well, but you can get an impression what it needs to do.

http://postimage.org/image/yllgrrhz3/