4
$\begingroup$

I have an array of points with their coordinates X and Y. Each point represents a bus stop. I need to sort the points in a sequence by giving them sequence numbers, so that the path from the first to the last is the shortest.

For a convention, let's call the array "points", so we access and write by calling

point(i) for the point
point(i)(x) and point(i)(y) for the coordinates
point(n) is the sequence number.

It's also possible to use the "for each" loop:

for each point in points
point(x)
point(y)
point(n) 

The sequence needs to go through all the points of the array. I searched a lot on the internet, and the only thing I could find is Dijkstra's algorithm, which is not exactly what I am looking for, since I need to go through all the points.

It would be great if one of you guys knew something about that...

Thanks a lot.

Julien

$\endgroup$
2
  • $\begingroup$ Traveling Salesman? $\endgroup$
    – Wlod AA
    Sep 6, 2021 at 6:40
  • $\begingroup$ In my experience, simulated annealing is excellent. $\endgroup$
    – Wlod AA
    Sep 6, 2021 at 6:42

1 Answer 1

7
$\begingroup$

If you only care about the length of the path between the first and last bus stops, then it looks like you are trying to solve the shortest Hamiltonian path problem (HPP). This is related to the more widely studied traveling salesman problem, see TSP. Since your points actually lie in the plane, you are considering the special case of the Euclidean Hamiltonian path problem. For Euclidean TSP, there is a polynomial-time approximation scheme, so I am guessing that the same is true for Euclidean HPP. Also, there are some heuristics based on neural networks, that appear to work well. See this paper.

$\endgroup$
2
  • $\begingroup$ Thank's, you're so helpful ! (I can't vote up since i don't have 15 reputation...) $\endgroup$
    – Julien
    May 24, 2010 at 0:12
  • $\begingroup$ The link to sciencedirect.com is broken. I'm also unable to find any snapshot saved on the Wayback Machine. $\endgroup$ May 15, 2023 at 5:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.