in reply to Travelling problem

The shortest_path method is not designed for solving the travelling salesman problem. It just finds the shortest way to get from A to D following the edges you've defined. A-B-D (weight 700) is shorter than A-C-D (1300), A-B-C-D (1300), or A-C-B-D (1700). The direct route A-D (weight 700) has an equal to A-B-D; in the case of multiple routes with equal weight, I don't know whether which one is returned is random or deterministic.

Graph may have what you need.

use Moops; class Cow :rw { has name => (default => 'Ermintrude') }; say Cow->new->name

Replies are listed 'Best First'.
Re^2: Travelling problem
by Dirk80 (Pilgrim) on Dec 21, 2013 at 21:14 UTC

    Thank you very much! This sounds very interesting. I'll try that SPT_Dijkstra algorithm tomorrow.

[reply]

      I tried the Graph module. I had a deep look at the SPT_Dijkstra algorithm and tried it with some sample data.

      I think that I now understand the algorithm. It takes a start vertex and the result are the paths from the start vertex to all other vertices.

      But this is not what I need. I need only one path from the start to the end which takes all vertices between into account.

      I see no way how to solve my problem with the graph module. Or do I see something wrong? I'll now try another way. Nevertheless thank you. It was interesting to play with this Graph module.

      Update:

      The Graph module does not seem to be the problem, but my lack of knowledge about graph algorithms. I'm reading now about these algorithms. When I understood them, then I'll start my implementation.

[reply]

In Section Seekers of Perl Wisdom