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

Question

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

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

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

标签： algorithmgraphpath-finding

Answer 1

这是一个可能不是最佳但易于理解的答案，可能足以满足您的需求。

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

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