Search code examples
pythonpathshortest

Find the minimal common path from any nodes to one node

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)

Solution
    • 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.