我有一个图，其中每个节点都是3D点，边缘表示3D空间中这些点之间的距离。图形未完全连接。这意味着在A点和B点之间可能有一条直接走线或多段走线的方式（例如A->C->D->E->B）。
我想找到一条通过给定点集的最短封闭路径（所有点都应位于路径上）。
Boost Graph库中是否有现成的实现方案？
P.S。路径应从相同的顶点（循环）开始和结束
Boost Graph：经过一组点的最短路径
•
问答
abc123321tang 回答：Boost Graph：经过一组点的最短路径
这是旅行商问题，这是NP难题。
BGL中有一种最佳解的近似算法：https://www.boost.org/doc/libs/1_71_0/libs/graph/doc/metric_tsp_approx.html
它假设距离有一些metric properties：
TSP的一个很自然的限制是要求城市之间的距离形成一个满足三角不等式的度量；从A到B的直接连接永远不会比通过中间C的路线更远：
这很适合您的问题，因为您的图形模型指向3D空间