Boost Graph: Shortest path that pass through a set of points

Question

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)

Answer 1

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:

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