HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Optimal root in shortest path tree (SPT)

Submitted by: @import:stackexchange-cs··
0
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?

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

Context

StackExchange Computer Science Q#116896, answer score: 3

Revisions (0)

No revisions yet.