Finding Shortest Path through whole points without revisiting
20 views (last 30 days)
Show older comments
Hi all,
I have a problem and I need urgent help. I have more than 30 points (2D cartesian coordinate) with known x and y coordinates. All points can be distributed randomly or on a regular basis such as star shape or cross shape. I would like to asing a one way path which connects all points without circling or revisiting them. How can I implement this question? I would like to visit each point only once and complete the whole journey as quick as possible.
Thanks in advance.
0 Comments
Accepted Answer
Bruno Luong
on 18 Aug 2020
Edited: Bruno Luong
on 18 Aug 2020
You can look at TMW tuto on Traveling Salesman Prroblem
or file exchanges of this author
2 Comments
Walter Roberson
on 18 Aug 2020
Note that the request is for a Hamiltonian Path not Travelling Salesman. Travelling Salesman can revisit a point.
Bruno Luong
on 18 Aug 2020
"An equivalent formulation in terms of graph theory is: Given a complete weighted graph (where the vertices would represent the cities, the edges would represent the roads, and the weights would be the cost or distance of that road), find a Hamiltonian cycle with the least weight."
More Answers (2)
Walter Roberson
on 18 Aug 2020
this problem is known as the Hamiltonian Path
https://www.mathworks.com/matlabcentral/fileexchange/51610-hamiltonian-graph-source-destination
See Also
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!