我的问题如下。
我有一个“备份”节点和其他节点。 从这些节点，我需要生成一个最小的备份节点的公共(public)路径(未加权和无向图) 我不需要每次都有解决方案。我怎么知道我是否可以生成这条路径。
我正在考虑将图拆分为一些子图并搜索最小的“子路径”。
但是我的图论不太好。 我使用 Python 和 C++。
提前致谢。
(抱歉，如果已经有这样的问题，我已经搜索过，但没有找到)
请您参考如下方法:
- 如果您需要找到与“备份”节点距离最短的节点，那么 BFS 将是合适的。
- 据我了解，您需要找到从图中的几个(如果不是全部)节点到“备份”节点的最小路径。 为此，我认为，您需要研究处理 Minimum Spanning Trees 的算法。
- 另外，我发现了另一个与您的问题类似的 StackOverflow 问题: SO#1
- 您可能还会发现此页面很有用: Shortest Path Tree .它不提供任何代码示例，但它是一个起点。一旦您了解了它背后的理论，我相信您要么会想出代码，要么能够找到它。
