CODEWITHSUNDEEP
algorithmtree
Vihari Piratla
Vihari Piratla

Reputation: 9322

Common segment of longest paths in a tree

I came across a programming questions where one will be

  1. given a weighted tree.
  2. Set of nodes one is interested in, let us call this set S.

We need to return the shortest of the common segment of the longest of the ideal paths. ideal path is the path that starts and terminates on a vertex that belongs to set S above. It is n't assured that the common path exists. I am aware of finding the longest path in a tree in linear time and also we can easily extend it to the case of ideal paths, but the classical algorithm of 2 dfs's, is not going to help in finding the longest paths, but just the longest path lengths. Thank you.

Upvotes: 1

Views: 238

Answers (1)

Ari
Ari

Reputation: 3127

If you have:

  1. Path begin
  2. Path length, got from algorithm like DFS or BFS
  3. Path end

You can easily get path. Change code:

//current vertex is v, next is u, current length is l
u.length = l + 1;
u.visited = true;
cont.push(u);

Adding line:

u.previous = v;

Then you can find path by:

v = path_end;
while(v != path_begin){
    //mark, v belongs to "path"
    v = v.previous
}

Upvotes: 0

Related Questions