From: gordon@cs.uwa.edu.au (Gordon Royle)
Newsgroups: comp.programming,comp.theory,sci.math
Subject: Re: How to find diameter of a graph?
Date: 3 Mar 96 05:57:17 GMT

crawford@cais3.cais.com (Randolph Crawford) writes:

>In article <4h2r3j$p93@monet.op.net>, Mark-Jason Dominus <mjd@op.net> wrote:
>>
>>Suppose I'm given a graph.  I want to find the graph's diameter.  As
>>I'm sure you recall, the distance d between two vertices u and v is
>>the length of the shortest path from u to v.  The diameter of the
>>graph is this distace d for the two vertices u and v which are
>>farthest apart.  
>>
>>That is, if the graph is G(V,E), then I want
>>
>>	max(u,v in V) of d(u,v).
>>
>>I believe there is a fast algorithm for computing this, but I don't
>>know what it is.  None of my graph theory references are helping me.

>You want to find the all-pairs longest path.  (Right?  Or is it the 
>longest path between two given points?)  There are efficient


	No, he wants to find the diameter not the longest path.

	The statement

		max(u,v in V) of d(u,v)

	implies that he wants to find the maximum of the d(u,v). However
	each d(u,v) is the length of the SHORTEST path from u to v.

	Either do an all-pairs shortest path routine  (see a book like
	Introduction to Algorithms, Cormen, Leiserson, Rivest) and
	then find the biggest number, or simply do n breadth-first search 
	algorithms, one from each vertex.

	The lecture notes on the (Algorithms) course that I teach
	are on

		http://www.cs.uwa.edu.au/~gordon/cs300

	and may help you (look at lecture 6 on the Graph Algorithms
	section).

	Cheers

	Gordon
-- 
Gordon Royle ---- gordon@cs.uwa.edu.au
Visit http://www.cs.uwa.edu.au/~gordon
--