Calculate sub-paths between two vertices from minimum spanning trees

Question

I have a minimum spanning tree (MST) from a given graph. I am trying to compute the unique sub-path (which should be part of the MST, not the graph) for any two vertices but I am having trouble finding an efficient way of doing it.

So far, I have used Kruskal's algorithm (using Disjoint Data structure) to calculate the MST (for example: 10 vertices A to J).. But now I want to calculate the sub-path between C to E.. or J to C (assuming the graph is undirected).

Any suggestions would be appreciated.

Answer 1

If you want just one of these paths, doing a DFS on your tree is probably the easiest solution, depending on how you store your tree. If it's a proper graph, then doing a DFS is easy, however, if you only store parent pointers, it might be easier to find the least common ancestor of the two nodes.

To do so you can walk from both nodes u,v to the root r and then compare the r->u and r->v paths. The first node where they differ is the least common ancestor.

With linear preprocessing you can answer least common ancestor queries in constant time. If you want to find the paths between pairs of nodes often, you might want to consider implementing that data structure. This paper explains it quite nicely, I think.