Simple shortest path problem in matrix.

2013 2 16
3 个回答
2 次查看（30 天）

0 个投票

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!

10 个评论
显示 8更早的评论 隐藏 8更早的评论

Azzi Abdelmalek
Azzi Abdelmalek 2013-2-16
What is the size of your matrix?
Walter Roberson
Walter Roberson 2013-2-16
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
Seeker 2013-2-16
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
Seeker 2013-2-16
编辑：Azzi Abdelmalek 2013-2-16
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
Image Analyst 2013-2-16
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
Seeker 2013-2-16
编辑：Seeker 2013-2-16
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
Azzi Abdelmalek 2013-2-16
编辑：Azzi Abdelmalek 2013-2-16
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
Seeker 2013-2-16
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
Azzi Abdelmalek 2013-2-16
编辑：Azzi Abdelmalek 2013-2-16
Ok. I understand, but this is not a simple problem like you said!
Seeker
Seeker 2013-2-16
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.

请先登录，再进行评论。

请先登录，再回答此问题。

回答（3 个）

Image Analyst
Image Analyst 2013-2-16

0 个投票

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

Seeker
Seeker 2013-2-16
编辑：Seeker 2013-2-16
I did. But everything there looks like a overkill. Mine is much simpler problem and those functions are not really applicable.
Thank you, anyway.

请先登录，再进行评论。

Alex Foreever
Alex Foreever 2013-2-16

0 个投票

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.

5 个评论
显示 3更早的评论 隐藏 3更早的评论

Seeker
Seeker 2013-2-16
Thanks for the suggestion. :)
Image Analyst
Image Analyst 2013-2-16
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
Seeker 2013-2-16
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
Walter Roberson 2013-2-16
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
Image Analyst 2013-2-17
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.

请先登录，再进行评论。

Walter Roberson
Walter Roberson 2013-2-16

0 个投票

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.

1 个评论
显示 -1更早的评论 隐藏 -1更早的评论

Seeker
Seeker 2013-2-16
编辑：Walter Roberson 2013-2-16
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/

请先登录，再进行评论。

类别

在 帮助中心 和 File Exchange 中查找有关 Graph and Network Algorithms 的更多信息

标签

提问:

Seeker
Seeker
2013-2-16

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by