1

I have a graph where each node is an 3D point and the edges represents the distances between those points in 3D space. The graph is not fully connected. This means between point A and B, there may be a single direct way to go or multi stage way (e.g. A->C->D->E->B).

I want to find the shortest closed path that passes through a given set of Points (all of points should lay on the path).

Is there a ready implementation for that in Boost Graph library?

P.S. The path should start and end from the same vertex (Cycle)

Humam Helfawi
  • 19,566
  • 15
  • 85
  • 160

1 Answers1

2

This is the Traveling Salesmen Problem, which is NP-hard.

There's one approximation algorithm of optimal solutions in BGL: https://www.boost.org/doc/libs/1_71_0/libs/graph/doc/metric_tsp_approx.html

It assumes that the the distances have some metric properties:

A very natural restriction of the TSP is to require that the distances between cities form a metric to satisfy the triangle inequality; that is the direct connection from A to B is never farther than the route via intermediate C:

enter image description here

This suits your problem because your graph models points in 3D space

sehe
  • 374,641
  • 47
  • 450
  • 633
  • 2
    You should add that since he is not interested in cycles but onlys in a path, he would have to add a dummy node as described [here](https://stackoverflow.com/questions/6733999/what-is-the-problem-name-for-traveling-salesman-problemtsp-without-considering/7158721#7158721). This would of course invalidate the triangle inequality. – Albjenow Nov 07 '19 at 14:14
  • @Albjenow Actually, I needed a cycle but did not express myself correctly.. Thanks guys! – Humam Helfawi Nov 07 '19 at 16:23