From: Rick Decker Newsgroups: sci.math Subject: Re: Route finnding algorithms Date: Sat, 07 Dec 1996 16:25:41 +0000 Gary Hampson wrote: > > In article , Mr Chris Goodwin > writes > > Its basically a route planning problem - I have a series of > >nodes which have some connections between them, though the nodes > >are not fully connected. If I want to get from one node to > >another, what is the shortest route, or quickest? I guess > >it is very similar to stating, "I want to get from London > >to Edinburgh, what is the best route?" which has been well solved > >by the AutoRoute program. > > You need a global optimisation algorithm to solve this problem, often > termed "The Travelling Salesman" problem. Nope, this isn't TSP. This is the "single-source least-cost" problem, and it can be solved in time polynomial in the number of vertices, unlike TSP, which doesn't have a poly-time solution unless it turns out that P = NP. The canonical algorithm is due to Dijkstra and can be found in almost any graph theory or algorithms text (I hear there's a good one titled _Working Classes_, where the solution can be found on pp. 320-326). Regards, Rick ----------------------------------------------------- Rick Decker rdecker@hamilton.edu Department of Comp. Sci. 315-859-4785 Hamilton College Clinton, NY 13323 = != == (!) ----------------------------------------------------- ============================================================================== [Decker is referring to his book; see http://www.brookscole.com/compsci/compsci/dhwork.html --djr]