查找从任何节点到一个节点的最小公用路径 [英] Find the minimal common path from any nodes to one node

问题描述

我的问题如下.

我有一个"备份"节点和其他节点. 从这些节点中，我需要生成一条到备份节点的公用路径，该路径最小(未加权和无向图) 我不需要每次都解决.这就是我如何知道是否可以生成此路径的方法.

I have a "backup" node and others nodes. From theses nodes, I need to generate a common path to the backup node which is minimal (unweighted and undirected graph) I don't need a solution everytime. Just how I can know if I can generate this path or not.

我当时正在考虑将图分成几个子图，并搜索最小的" subpath ".

I was thinking about splitting the graph into some sub-graphs and searching for minimal "subpath".

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

But I'm not so good in graph theory. I use Python and C++.

谢谢你.

(对不起，如果已经有这样的问题，我已经搜索了，但是没有找到)

(Sorry If there is already a question like this, I have searched, but not found)

推荐答案

• 如果您需要找到与备份"节点的距离最短的节点，则BFS是合适的.
• 据我所知，您需要找到一条从图中的几个(如果不是全部)nos到"backup"节点的最小路径. 为此，我认为，您需要研究与最小生成树
• 此外，我还发现了另一个类似于您的StackOverflow问题: SO#1
• 您可能还会发现此页面有用: 最短路径树.它没有提供任何代码示例，但这是一个起点.一旦您掌握了理论，我相信您可以拿出代码或能够找到它.
• If you need to find a node with a minimal distance to the "backup" node, then BFS would be appropriate.
• As I understood, you need to find a minimal path from several( if not all) noes in your graph to the "backup" node. For that, I think, you need to look into algorithms that deal with Minimum Spanning Trees
• Also, I've found another StackOverflow question that resembles yours: SO#1
• You may also find this page useful: Shortest Path Tree. It doesn't provide any code samples, but it is a starting point. Once you get the theory behind it, I am sure you will either come up with code or will be able to find it.

这篇关于查找从任何节点到一个节点的最小公用路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！