Hey everybody,
sorry if this post is kinda vague. But I'm not sure where to start looking. I need an algorithm for a "travelling salesman" type problem. The idea is, I have a bunch of nodes and each node is separated from another by a certain distance (if they are connected at all). The task is to find the shortest route between two nodes. This is essentially happening on a map, but without the actual "map" part. Just the distances between intersections is recorded.

I'm not looking for a whole algorithm, but rather if anyone can point me in the right direction I would appreciate it. Numerical Recipes suggests simulated annealing for the travelling salesperson problem, and I'm going to look into this to see if it's applicable. But any other pointers would be great.

Posted on 2002-06-11 18:35:02 by chorus
Some time ago there was a thread called "That is not Assembly 101".
I'll move this thread to Main, because this forum is not made for requests :)

Posted on 2002-06-12 01:02:27 by bazik
I think Dikstra's algorithm is what you're looking for (I'm not sure if I spelled it right, I think there's a y instead of an i)
It's supposed to find the shortest path between two specified nodes in a directed graph (a graph is a collection of nodes connected to each other like a tree except that there can be cyclic connections).

I used to have more info on the subject back when I was in highschol but I can't find it right now.

I think the basic idea the principle that the shortest point from point j to point m was the shortest point from point j to point k plus the distance from point k to point m, if k is in the path.

I'm not sure how dikstra's is used itself, I think it involves two for loops and some kind of used and unused stacks that keep track of the nodes used.

An easier but less common method would be using floyd's algorithm which calculates the shortest distance between any two nodes.

basically if you had a two dimensional array (a) where a indicated the shortest distance from i to j. and you started with basic distance information and all non connected nodes with a value of infinity you can just do:

for i:=1 to n do (n is the number of nodes)
for j:=1 to n do
for k:=1 to n do
if a+a<=a then

If you wanted to know the actual path then you can just store an array of nodes for each element in the array keeping track of the path taken.

This method is ofcourse slow and time consuming. If you could find the appropriate dykstra's algo then I think there's an easy way to modify it to keep track of the particular path between the nodes you are looking for.
Posted on 2002-06-12 03:45:08 by Satrukaan




i like twoopt or threeopt exchanges (search the net, you can find pascal source codes)...
Posted on 2002-06-12 04:54:46 by kamilh
Thank you for the very good links kamilh.
Posted on 2002-06-12 07:21:40 by bitRAKE
Thank you Satrukaan and kamilh!
Your info was very helpful, and I have decided on an approach from the sources you provided me that will work very well :)

Sorry if the post was made to the wrong group... I'll try and be more careful next time ;)

Posted on 2002-06-13 16:56:22 by chorus