Find the minimal common path from any nodes to one

问题:

My problem is the following.

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.

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

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

Thanks you from advance.

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

回答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.

回答2:

so the problem is not about "shortest", it's about whether they are connected or not.

you can do bfs or dfs starting from the "backup" node, each node you've reached can generate a path to the "backup" node.

check out:

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