Dijkstra's Shortest Path algorithm

[Paul Magwene]

Roy Katz wrote:
> 
> On Wed, 13 Dec 2000, Andy Robinson wrote:
> 
> > Yes, there is.
> >
> > Aaron Watters kjBuckets collections library include a graph type
> > written in C, which has this and several other useful algorithms.
> > www.chordate.com
> >
> > - Andy Robinson
> >
> 
> Wonderful! That's important for my sanity.
> But that sort of takes the fun out of making something people will
> use. Unless something else needs to be made? Is there anything that people
> need implemented? I'm finally ending my semester next week, so it'd be
> great to get back into serious Python programming (as opposed to this
> semester's C++).
> 


If you're interested in graphs and programming, how about a clique
finding algorithm for undirected graphs?  

I implemented a VERY slow clique finding algorithm myself, and then ran
across Andrew Dalke's web page which  has some C code based on the
Bron-Kerbosch algorithm (see
http://starship.python.net/crew/dalke/clique/ ).  I'm still trying to
wrap my mind around the algorithm in this paper (I'm not a computer
scientist), but I'd love to see a `pure python' version (I think this
would help me to understand what's going on), or better yet a fast
version which utilizes Numeric.



Paul Magwene
paul.magwene at yale.edu