### witcher98's blog

By witcher98, history, 6 weeks ago, ,

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?

• -6

 » 6 weeks ago, # | ← Rev. 2 →   0 smallest path between those nodesThere 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, # ^ |   0 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, # ^ |   0 There are multiple ways you can compute LCA (you can google for those). Just pick one that suits you best.
•  » » » 6 weeks ago, # ^ |   0 codechef hmmmm i seee
 » 6 weeks ago, # |   0 Read this blog Algorithm Gym :: Graph Algorithms
 » 6 weeks ago, # | ← Rev. 2 →   0 Incase you have weighted graph: Use $dijkstra$, otherwise use $BFS$, no need to overcomplicate it.