Simple shortest path problem in matrix.

1 次查看（过去 30 天）

Seeker 2013-2-16

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63706-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!

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

Azzi Abdelmalek 2013-2-16

编辑：Azzi Abdelmalek 2013-2-16

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

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 2013-2-16

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63706-simple-shortest-path-problem-in-matrix#answer_75291

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

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

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 2013-2-16

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63706-simple-shortest-path-problem-in-matrix#answer_75306

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 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 2013-2-16

在 MATLAB Online 中打开

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 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 2013-2-16

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/63706-simple-shortest-path-problem-in-matrix#answer_75314

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.