algorithm - 如何找到包含图子集中所有节点的图的最小电路？

Question

给定一个加权无向图 G = (V, E) 和一组节点 P 和一个起始节点 S 和节点 P_S 的子集。

我想在此图 G 中找到最小权重电路，使其包含 P_S 中的所有节点。允许电路回溯（即可能有一段A->B->C->B->A）。

我们曾考虑过将其与 TSP 联系起来，但略有不同，因为我们实际上是在尝试获得一个电路，并且允许它回溯。我们还考虑使用 Dijkstra 找到我们需要的所有节点（起始节点和 P_S 中的节点）之间的最短路径，但这会返回一个不是电路的树。

我们怎样才能找到这样的电路？

标签： algorithmgraphshortest-pathcyclecircuit