Beefy Boxes and Bandwidth Generously Provided by pair Networks
We don't bite newbies here... much
 
PerlMonks  

Re^5: Travelling Salesman

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


in reply to Re^4: Travelling Salesman
in thread Travelling Salesman

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...)

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://969570]
help
Chatterbox?
[Lady_Aleena]: This evening, I thought to myself, "I would love to search Netflix for 100 randomfilms from my database to see if they have them." So I went to CPAN to see if there were a modiule which could do such a thing. There is, but GUH! ...
[Lady_Aleena]: ... Does it have to be that hard and complex to use to do a search on Netflix?
Lady_Aleena grumbles.
[Lady_Aleena]: I really need to get back into the swing of Perl. I'm forgetting things from lack of use. I don't know how behind I am too.

How do I use this? | Other CB clients
Other Users?
Others imbibing at the Monastery: (6)
As of 2017-01-21 02:32 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    Do you watch meteor showers?




    Results (180 votes). Check out past polls.