I have $M$ vertices $V_1$ through $V_m$, which are paired into $N$ edges edges $E_1$ through $E_n$. I wish to add $N-1$ additional edges to the graph to produce a path graph that visits all of the vertices exactly once in an order that minimises the total length of the graph.

I currently have a solver using the nearest neighbour algorithm, starting with the edge with a vertex closest to a corner of the bounding box as the start, and then adding a new edge to the closest vertex of the closest unconnected edge, and continuing until the graph is connected.

Given the constraints, is there a better approach than a branch-and-bound iterative approach to finding a more optimal solution? Are there any additional heuristics that could be used to cull the problem space?

  • $\begingroup$ It seems you have requirements not stated in your first sentence, as you don't have to have a "start" and "end" vertex in such a graph. It will be a directed tree (and therefore acyclic) but not even necessarily a rooted directed tree, much less a single "line" or path with a start and end. $\endgroup$ – Wildcard Aug 26 '17 at 0:42
  • $\begingroup$ If, when you say the resulting graph is connected, you mean that, for any two vertices $u,v$ there is a path in one direction ($u\to v$ or $v\to u$), then the solution graph must be a path, and the options are just how to order the initial edges. $\endgroup$ – Joffan Aug 26 '17 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.