Hi,
I was hoping somebody could explain me an algorithm to find the 'central node' of a tree, i.e.  the node from which the maximum distance to any other vertex is minimized over all vertices.
Thank You
How to find the 'central node' of a tree?
Moderator: Board moderators
Identify the longest path of the tree. Then it's median node is the central node.
To identify the longest path, apply dfs from any node. Pick one of the deepest node from the dfs tree. Apply dfs again from this node. The path from this node to the deepest node of the second dfs tree is the longest path.
To identify the longest path, apply dfs from any node. Pick one of the deepest node from the dfs tree. Apply dfs again from this node. The path from this node to the deepest node of the second dfs tree is the longest path.

 New poster
 Posts: 4
 Joined: Sun Jul 31, 2005 6:37 am
 Contact:
The first solution that comes to mind is to run FloydWarshall on the graph, then search for the optimal node. Almost as soon as I started typing that, I realized it sucked. So instead, I made up another algorithm and realized 20 minutes later it was broken. Sorry.
FloydWarshall takes O(n^3) time and O(n^2) space in the number of nodes when coded correctly.
Edit: Cho owns me
FloydWarshall takes O(n^3) time and O(n^2) space in the number of nodes when coded correctly.
Edit: Cho owns me
No my algorithm doesn't work on weighted trees. For weighted trees you could try something like this: add another node and join every leaf with this node and the weigth of each added edge will be 0. Now just apply the Dijkstra algorithm with heaps and the node that is farthest away from the new node will be the center. So the algoritm will be O(M log N) but the number of edges is O(M) so we have a O(N log N) solution.