Menu
Suppose I am given a undirected tree and I need to find a path(the only path) between two nodes.
What is the best algorithm to do it.I probably could use a Dijkstra's algorithm but there a probably something better for trees.
C++ example would be helpful but not necessary
Thank you
358
Dijkstra's algorithm, published in 1959 and named after its creator Dutch computer scientist Edsger Dijkstra, can be applied on a weighted graph. The graph can either be directed or undirected. One stipulation to using the algorithm is that the graph needs to have a nonnegative weight on every edge.
Dijkstra's algorithm to find the shortest path between a and b. It picks the unvisited vertex with the lowest distance, calculates the distance through it to each unvisited neighbor, and updates the neighbor's distance if smaller. Mark visited (set to red) when done with neighbors.
A path in a graph is a sequence of vertices connected by edges, with no repeated edges. A simple path is a path with no repeated vertices. A cycle is a path (with at least one edge) whose first and last vertices are the same.
There is this standard algorithm for finding longest path in undirected trees using two depth-first searches: Start DFS from a random vertex v and find the farthest vertex from it; say it is v′. Now start a DFS from v′ to find the vertex farthest from it. This path is the longest path in the graph.
Assuming each node has a pointer to its parent, then simply back-track up the tree towards the root from each start node. Eventually, the two paths must intersect. Testing for intersection could be as simple as maintaining a std::map of node addresses.
UPDATE
As you've updated your question to specify undirected trees, then the above isn't valid. A simple approach is simply to perform a depth-first traversal starting at Node #1, eventually you'll hit Node #2. This is O(n) in the size of the tree. I'm not sure there's going to be a faster approach than that, assuming a completely general tree.
184
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
