Simple shortest path problem in matrix.
4 vues (au cours des 30 derniers jours)
Afficher commentaires plus anciens
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 commentaires
Azzi Abdelmalek
le 16 Fév 2013
Modifié(e) : Azzi Abdelmalek
le 16 Fév 2013
Ok. I understand, but this is not a simple problem like you said!
Réponses (3)
Image Analyst
le 16 Fév 2013
Try the File Exchange first: http://www.mathworks.com/matlabcentral/fileexchange/index?utf8=%E2%9C%93&term=shortest+path
1 commentaire
Alex Foreever
le 16 Fév 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 commentaires
Walter Roberson
le 16 Fév 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
le 17 Fév 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
le 16 Fév 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 commentaire
Voir également
Catégories
En savoir plus sur Operating on Diagonal Matrices dans Help Center et File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!