patternMinor
Optimal root in shortest path tree (SPT)
Viewed 0 times
pathoptimalshortestrootspttree
Problem
I would like to find the "optimal" shortest path tree (SPT) in some undirected weighted graph. As "optimal" SPT, I mean so its maximal path from root to leaf is minimal from any other potential SPTs.
It is quite easy to find SPT from 1 root via Dijkstra's algorithm. So I can run Dijkstra from all vertices and find the "optimal" SPT and its root.
Is there any faster algorithm?
It is quite easy to find SPT from 1 root via Dijkstra's algorithm. So I can run Dijkstra from all vertices and find the "optimal" SPT and its root.
Is there any faster algorithm?
Solution
This problem is equivalent to computing the radius of a graph. The best known algorithms for computing radius essentially compute all pairs shortest paths, so the method that you suggest cannot be improved much. If the number of edges is large, maybe Floyd–Warshall algorithm could be faster.
References:
https://en.wikipedia.org/wiki/Distance_(graph_theory)
https://arxiv.org/abs/1506.01799
References:
https://en.wikipedia.org/wiki/Distance_(graph_theory)
https://arxiv.org/abs/1506.01799
Context
StackExchange Computer Science Q#116896, answer score: 3
Revisions (0)
No revisions yet.