查找包含特定节点集合的最短“路径”

Question

我有图像中的顶部图（无权无向图），我想找到一组节点（数量最少的节点），以便所有选定的节点（红色）都连接在一起。

在这种情况下，我可以假设总是有一种方法可以到达“主节点”（大节点），这意味着总是有解决方案。我的解决方案如图像底部所示。

是否有这种问题的算法？我对“图形场景”很新，找不到任何算法，也许是因为我缺乏描述我所寻找的内容的术语。

- joao

---

你基本上是在寻找生成树的一个子集。 - undefined

https://en.wikipedia.org/wiki/Steiner_tree_problem - undefined

“主节点”必须包含在解决方案中吗？ - undefined

Answer 1

这里有一个答案，可能不是最优的但容易理解，并且可能足够满足你的需求。

1. 使用Floyd-Warshall算法解决所有节点间最短路径问题。
2. 以每个节点作为源节点，计算到每个红色节点的距离之和（如果存在无法到达的红色节点，则跳过源节点）。
3. 主节点是第2步中距离之和最低的源节点。

这仅适用于无权图，也就是说距离等同于路径中的节点数。

- wookie919

---

如果所有边的权重都为1，解决全源最短路径问题（APSP）时无需运行Floyd-Warshall算法。只需为每个节点运行广度优先搜索（BFS）。这个算法的时间复杂度是O(n(n+m))，稍微好于Floyd-Warshall算法的O(n³)，前提是边的数量不超过O(n²)。仅仅找到主节点也不足以解决这个问题。 - undefined