Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.2 9/18/84; site down.FUN
Path: utzoo!watmath!clyde!burl!ulysses!allegra!princeton!down!honey
From: honey@down.FUN (code 101)
Newsgroups: net.misc
Subject: Re: Small World Redux (and reflexive transitive closure)
Message-ID: <476@down.FUN>
Date: Sun, 24-Mar-85 12:59:10 EST
Article-I.D.: down.476
Posted: Sun Mar 24 12:59:10 1985
Date-Received: Mon, 25-Mar-85 02:01:50 EST
References: <542@ahutb.UUCP> <1308@ut-sally.UUCP> <879@ames.UUCP>
Organization: Princeton University, EECS
Lines: 7
Summary: read the code

pathalias does not use floyd/warshall's closed semi-ring algorithm, it
uses johnson's variant of dijkstra's algorithm.  i have described the
algorithm in net.mail in the recent past; read the code for details.
suffice it to say the the asymptotic time complexity is O(v log v),
assuming the graph is sparse.

	peter