我的问题如下。
我有一个 ”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。它不提供任何代码示例，但它是一个起点。一旦你掌握了它背后的理论，我相信你要么会想出代码，要么能够找到它。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
