求任意节点到一个节点的最小公共路径

我的问题如下。

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

我正在考虑将图分成一些子图并搜索最小的“subpath".

但我对图论不太擅长。 我使用Python 和C++。

预先感谢您。

（抱歉，如果已经有这样的问题，我已经搜索过，但没有找到）

• 如果您需要找到与“备份”节点距离最小的节点，那么 BFS 就合适。
• 据我了解，您需要找到从图中的几个（如果不是全部）节点到“备份”节点的最小路径。 为此，我认为，您需要研究处理以下问题的算法最小生成树 http://en.wikipedia.org/wiki/Minimum_spanning_tree
• 另外，我还发现了另一个与您的问题类似的 StackOverflow 问题：SO#1 https://stackoverflow.com/questions/1579399/shortest-path-fewest-nodes-for-unweighted-graph
• 您可能还会发现此页面很有用：最短路径树 http://en.wikipedia.org/wiki/Shortest_path_tree。它不提供任何代码示例，但它是一个起点。一旦你掌握了它背后的理论，我相信你要么会想出代码，要么能够找到它。