Graph distances, how can I speed it up?

[Fernando Pereira]

On 6/3/02 12:15 PM, in article
d571ae53.0206030815.2e52aac at posting.google.com, "Jonathan Ellis"
<ellisjb at my-deja.com> wrote:
> The obvious idea then is to not calculate anything until all edges
> have been added.  Then use dijkstra's algorithm
> (http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html)
> to compute and store distances as needed.  (You can probably get some
> savings over the classic algorithm if you know you are going to NEED
> distances for ALL vertices -- otherwise you are better off doing lazy
> (as-needed) computation.)
Dijkstra's algorithm is not a good choice here, because distances from all
sources appear to be needed, not from a single source. There is no good,
general way of saving parts of the work done for one source node to speed up
computing the distances from another source node (but see Johnson's
algorithm). So, he may need an all-sources algorithm like Floyd-Warshall,
which unfortunately is cubic on the number of nodes. Since the WordNet graph
is sparse, and in fact "almost" a tree, Johnson's algorithm might be better.
If the graph were a tree, the following much simpler algorithm would do. As
always, Cormen, Leiserson and Rivest (+ Stein in the new edition)
http://theory.lcs.mit.edu/~clr/ are your friends.

-- F