Re^3: Travelling Salesman

by JavaFan (Canon)
 on May 09, 2012 at 06:05 UTC ( #969566=note: print w/replies, xml ) Need Help??

in reply to Re^2: Travelling Salesman

But, but, but Dijkstra's algorithm solves a completely different task: find the shortest route between two points. And while you can construct graphs where there is a pair of points where the shortest path between them actually visits all other points, that's situation most traveling salesmen won't find themselves in. (Except maybe in Chili)

Either the OP is solving a different problem than the travelling salesman, or he's using something else than Dijkstra's.

Replies are listed 'Best First'.
Re^4: Travelling Salesman
by Anonymous Monk on May 09, 2012 at 06:32 UTC

I didn't do the analysis and I am guess but it should look something like this. On the whole graph, compute the shortest distance between two points in the graph(From the start point). Then the next shortest distance point from that and so on. Such that already visited points are removed from the graph every time a shortest distance point from the current point is computed.

Every time you find the shortest distance between two points, and reach the destination point. The source point is removed. At each step you end up having a smaller graph. There fore lesser points to work on each step. While at the same time you compute shortest distance point available from the current point.

That sounds like you're computing the smallest spanning tree. Which is *not* what Dijkstra's algorithm is doing. Given a smallest spanning tree, one can compute an approximation of the shortest hamiltonian path, which I think is at most a factor 2 off.

Dijkstra's algorithm in a nutshell:

1. Mark all nodes in the graph unvisited with distance infinite.
2. Mark the start node unvisited with distance 0.
3. Off all the unvisited nodes, pick the one (or one of) with smallest distance. Call this node X.
4. For all unvisited neighbours of X, calculate their distance to the start node (which is the distance X has, plus the length of the edge between X and its neighbour). If said distance is less than the current distance stored at the neighbour, update the distance.
5. Mark X as visited. If X is the destination node, you're done.
6. Goto 3. (Hah! A Goto in Dijkstra's algorithm. The irony...)

Create A New User
Node Status?
node history
Node Type: note [id://969566]
help
Chatterbox?
 [GotToBTru]: late to the conversation .. but thanks, Corion, for the reminder about Perl::Tidy [Corion]: GotToBTru: Heh ;) I'm not really endorsing it, as I found that any gains made through it are easily squandered by the hours spent on configuring it. At least in my case :) [GotToBTru]: Like most Swiss Army Knives, you can cut yourself trying to find the blade you actually want [GotToBTru]: i am satisfied with the default settings turning the seemingly random formatting into something reliable

How do I use this? | Other CB clients
Other Users?
Others taking refuge in the Monastery: (12)
As of 2017-02-27 14:30 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
Before electricity was invented, what was the Electric Eel called?

Results (387 votes). Check out past polls.