Graph distances, how can I speed it up?

[Jonathan Ellis]

tebeka at cs.bgu.ac.il (Miki Tebeka) wrote in message news:<33803989.0206030235.4134d33e at posting.google.com>...
> Hello All,
> 
> I'm trying to calculate distances in a graph. (The ultimate goal is 
> to calculate the distances between verbs in WordNet)
> 
> The graph is built edge after edge and each time I recalculate the 
> distances matrix. However this takes ages to complete. (will finish in ~50H).

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.)

-Jonathan