0

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

HK boy
  • 1,398
  • 11
  • 17
  • 25
mini
  • 180
  • 10

1 Answers1

0

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.

Alain T.
  • 40,517
  • 4
  • 31
  • 51