如何最小化遍历完整图形并找到最佳起点的路径？

Question

说出N个节点，并给出连接其中一些节点的路径的权重。平均而言，一个节点直接连接到m个比N小得多的m个节点。我想知道如何选择行进起点，因为我们必须覆盖所有节点并且以最小的路径权重总和。另外，N是一个非常大的数字（介于10k-50k之间）。

Answer 1

我会说蛮力是要走的路。给定图G =（V，E），选择每个顶点vεV，使用简单的广度优先搜索找到从v到所有其他节点的总权重。从v开始，转到所有相邻顶点，添加所有边的权重，然后重复。重复此步骤，您将获得最小值。