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

Question

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

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

这种问题有算法吗？
我是“图形场景”的新手，我找不到任何东西，也许是因为我缺乏描述我正在寻找的东西的术语。

Answer 1

好问题，但很难找到解决方案

Answer 2

这里的答案可能不是最佳的，但很容易理解，并且可能足以满足您的需求。

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

这只有效，因为图是未加权的，这意味着距离等于路径中的节点数。