algorithm - 无向加权图中连接 3 个顶点的最小总权重，只有正边权重

Question

我正在寻找关于从哪里开始寻找此问题的解决方案的指示。

谷歌搜索一段时间后，我发现唯一与我的问题相似的问题是 minimum spanning tree .不同之处在于，我不是在寻找跨越图中所有顶点的树，而是寻找跨越 3 个给定顶点的树。

我不是在寻找一个完整的程序，而是一个指向答案大方向的指针。

我的另一个想法是使用 Dijkstra's algorithm 运行 3 次搜索.这个想法是通过组合不同的最短路径以某种方式找到最佳路径。我不知道这将如何完成。

这是我正在谈论的图表类型的图形示例:

因此任务是找到一种方法来找到连接此类图中任意 3 个顶点的最小和权重。

编辑:
我通过使用 Dijkstra 算法运行 3 次搜索解决了这个问题。然后我通过将所有唯一边相加找到连接 3 个顶点的总和权重最小的顶点。感谢所有的帮助:)

Answer 1

我很确定您可以使用 Dijkstra 算法做到这一点，唯一的技巧是您不知道访问节点的顺序，因此您必须尝试所有 6 种顺序。

因此，如果您有节点 A、B 和 C，对于 A、B、C 的第一个排序，您将在 A 和 B 之间、B 和 C 之间以及 C 和 A 之间运行 Dijkstra。然后你将执行下一个排序 A、C、B。然后继续。