I'm stuck in my algorithm assignment which ask to find the direct path in a tree(V, E) with n vertices (acyclic indirect graph) from vertex v to vertex w in time complexity O(dist(v, w)). I have to find a preprocess (that runs in O(n)) to store some information such that I can achieve the time complexity O(dist(v, w)).
I'll need some idea to what store in the preprocess that will help later in the algorithm.
No full solution.
I already tried to store the possible path but to create a global Adj List I need quadratic time O(n^2). Also Dijkstra run above the time complexity requested (and all routing algorithm for network). Two nodes in a tree have a unique path.
Also tried to use dynamic programming to store all the path already discovered, but I think I get over the linear time. Running BFS and store all the previous path like: (node, node) : next hop
(A, B) : B and (B, A) : A
(B, C) : C (C, B): B (A, C) : B and (C, A): B
Therefore I'll need (1 + 2 + 3 + 4 + 5 + ... + n - 1 + n) = n^2
If your network is a tree, then each vertex only has one "inbound" edge. So you should try traversing the links from W to V (following the inbound edges) instead of the other way around. This will give you the path in reverse order. Store it in a list and invert it to produce the result.
Note that you may need to build a dictionary of vertices {child:parent} to do this if you don't already have a way to traverse the tree from bottom to top. Building this dictionary will take O(E) time, then finding the path will take dist(V,W) time.