Graph distances, how can I speed it up?

[Fernando Pereira]

On 6/3/02 1:12 PM, in article
eppstein-347A24.10122403062002 at news.service.uci.edu, "David Eppstein"
<eppstein at ics.uci.edu> wrote:

> In article <B92114F6.B79E%pereira at cis.upenn.edu>,
> Fernando Pereira <pereira at cis.upenn.edu> wrote:
> 
>> Dijkstra's algorithm is not a good choice here, because distances from all
>> sources appear to be needed, not from a single source.
> 
> Dijkstra is not a bad choice for all pairs shortest paths -- just repeat
> it for each source in the graph.
Think about the redundant traversal of some sub-graphs compared with
Floyd-Warshall. Worst-case bounds are not so interesting here, as we are
dealing with very particular graphs (WordNet). There's a huge literature on
all-pairs shortest-distance algorithms that may be worth looking at, for
instance <http://robotics.stanford.edu/~koller/papers/path.ps>.

-- F