Distances between any pair of nodes

Problems and Contests
#1

How can we find the distances between every pair of nodes given a graph with N nodes and M edges?

I believe that trees introduce many simplifications, especially since there’s only one simple path between any two nodes. Can we achieve this task in O(N+M) using a single DFS call on a tree?

Please explain how we can achieve this with DFS on a tree, and please provide some example code. Thank you!

#2

So do you want to find the distance between any two nodes on a tree or a generalized graph?

#3

A tree. I suppose it would be impossible on any simple graph since that might contain cycles.

#4

So just to clarify, you’re given a tree and a bunch of queries where you want to find the distance between those two nodes, correct?

#5

Yes. Queries are of the form “distance between a and b?” This is possible to do in O(N^2) by rooting the tree at N different nodes, but I am asking whether we can do it in O(N) (using DFS).

#6

You could do it in Q log N with lowest common ancestor? Which should be good enough for most cases?

#7

https://cp-algorithms.com/graph/lca_tarjan.html

This takes \mathcal O(N + M) to find the LCA of all queries.