Simple shortest path problem in matrix.
2 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
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 comentarios
Azzi Abdelmalek
el 16 de Feb. de 2013
Editada: Azzi Abdelmalek
el 16 de Feb. de 2013
Ok. I understand, but this is not a simple problem like you said!
Respuestas (3)
Image Analyst
el 16 de Feb. de 2013
Try the File Exchange first: http://www.mathworks.com/matlabcentral/fileexchange/index?utf8=%E2%9C%93&term=shortest+path
1 comentario
Alex Foreever
el 16 de Feb. de 2013
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 comentarios
Walter Roberson
el 16 de Feb. de 2013
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
el 17 de Feb. de 2013
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
el 16 de Feb. de 2013
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 comentario
Ver también
Categorías
Más información sobre Matrix Indexing en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!