witcher98's blog

By witcher98, history, 6 weeks ago, In English,

How can I get the path between two nodes if I've used LCA algorithm? What is the fastest way to get the smallest path between those nodes?

 
 
 
 
  • Vote: I like it
  • -6
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

smallest path between those nodes

There is only one path between any two nodes in a tree ... If your graph is not a tree, using LCA does not even makes sense.

How can I get the path between two nodes if I've used LCA algorithm?

Let's say you want the path from node u to node v. Starting from node u, go to its parent, then its grandparent and so on until you reach LCA(u, v). Call this path p1. Do the same for v. Call the path p2. The path from u to v is just the union of p1 and p2.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes the graph is a tree for sure. But I've one question- Do i need to use LCA with binary lifting algorithm and simple LCA if I want to calculate the path between those 2 nodes? Which one will have better time complexity in calculating the path?

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it
»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Incase you have weighted graph: Use $$$dijkstra$$$, otherwise use $$$BFS$$$, no need to overcomplicate it.