Re: Off topic. It's about math. Don't read if you don't like math please.Thanks.

[Alex Larsson <alexl redhat com>]

On Thu, 25 Apr 2002, Thai Dang Vu wrote:

> Hello,
>
> I'm studying Computer Science master course and I'm looking for an
> algorithm about finding the shortest path in a graph. This path must
> passes every point in the graph and never passes a point twice. It
> sounds like Dijikstra algorithm, but Dijikstra path doesn't pass all
> points.
>
> Do you have the name of that algorithm so that I can search for it on
> Internet?
>
> Thanks so much and sorry for an off topic letter.

This problem is called the "Traveling Salesman" problem, and it's NP 
complete, so you can't hope to find any efficient implementation of it. I 
think there are heuristical methods that do pretty well.

-- 
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
 Alexander Larsson                                            Red Hat, Inc 
                   alexl redhat com    alla lysator liu se 
He's a deeply religious zombie farmboy plagued by the memory of his family's 
brutal murder. She's a high-kicking Buddhist archaeologist from a different 
time and place. They fight crime!