python - 找到从任何节点到一个节点的最小公共路径

Question

我的问题如下。

我有一个“备份”节点和其他节点。从这些节点，我需要生成一个到备份节点的公共路径，该路径是最小的（未加权和无向图）我不需要每次都需要解决方案。我怎么知道我是否可以生成这条路径。

我正在考虑将图拆分为一些子图并搜索最小的“子路径”。

但是我在图论方面不是很好。我使用 Python 和 C++。

提前谢谢你。

（对不起，如果已经有这样的问题，我已经搜索过了，但没有找到）

Answer 1

• 如果您需要找到与“备份”节点距离最小的节点，那么 BFS 将是合适的。
• 据我了解，您需要找到从图中的几个（如果不是全部）noes 到“备份”节点的最小路径。为此，我认为，您需要研究处理最小生成树的算法
• 另外，我发现了另一个类似于你的 StackOverflow 问题： SO#1
• 您可能还会发现此页面很有用： 最短路径树。它不提供任何代码示例，但它是一个起点。一旦你掌握了它背后的理论，我相信你要么会想出代码，要么就能找到它。

Answer 2

所以问题不在于“最短”，而在于它们是否连接。

您可以执行bfs或dfs从“备份”节点开始，您到达的每个节点都可以生成到“备份”节点的路径。

查看：

http://en.wikipedia.org/wiki/Breadth-first_search
http://en.wikipedia.org/wiki/Depth-first_search