Best algorithm to find shortest path in a spanning tree from single source to all other nodes

Question

How can I find the shortest path from every vertex to every vertex if I know that the given graph is actually a spanning tree i.e. each pair of vertices have only one path between them? I want the most optimal solution. I know the Dijkstra's algorithm, but it is highly time complex.

I basically want to know the distance & path of every vertex from one source. What is the best and most optimal solution to this given that it is a spanning tree?

Additionally, kindly let me know if there is some different way to find all pair shortest path than applying the algorithm of single source shortest path for multiple times given that the graph is actually spanning tree.

Kindly, mind me for the over-explanation.

Answer 1

The right way to do this is to start by depth first search from some arbitrary node N, which you can do in linear time. Each time you encounter a new node, you log the path that you took to get there. This will give you the shortest path between N and each other node in the graph.

To find the shortest path between nodes V and W, you look at the path from V to N, and the path from N to W. This will give you the shortest path between V and W, except for possibly a redundant bit in the middle where you hit N and then come back again. For instance, suppose the path from V to N is this:

V, A, B, C, D, E, N

and the path from N to W is this:

N, E, D, F, G, W

then you can see that the path from V to W following the concatenation of these would get to D, then go up to N via E and back again. This needs to be removed from your path to give you the shortest path. In other words, you scan backwards from the end of the first path, and forwards through the second path, until you reach the last node that they have in common (D in this case) and you chop the paths and join them together at this point, so that you're left with

V, A, B, C, D, F, G, W

This will give you the shortest path. You can see this because any path from V to W that doesn't repeat any nodes must be the shortest path in a spanning tree.

Here's a spanning tree nicked from Wikipedia as an example. If you take V as top left, N as top right, and W as bottom left, you can see that the shortest path from V to W is the shortest path from V to N, concatenated with the shortest path from N to W, but without the duplicated section in the middle where we come up to N and back down to the main path.

Answer 2

An optimal solution:

1. Chose an arbitrary vertex as a root and run depth-first search from it to compute dist[i] for all i - the distance between the root and the i-th vertex.

2. The distance between two arbitrary vertices u and v is dist[u] + dist[v] - 2 * dist[lca(u, v)], where lca(u, v) is the lowest common ancsetor of u and v.

The first step has O(n) time complexity. The second step's time complexity depends on the lowest common ancestor search implementation. It is possible to achieve O(1) per query with linear preprocessing time(using this algorithm: http://www3.cs.stonybrook.edu/~bender/newpub/BenderFa00-lca.pdf), but this approach has a rather big constant and it is not very easy to implement. This solution is optimal because it requires O(n) time for preprocessing(it is not possible to do better since you have to at least read the input) and it answer a query in a constant time. You can also get O(log n) time per query with O(n) or O(n log n) preprocessing time using simpler algorithms.