M
Meng
Hi All,
I'm designing a project to solve TSP issue with Perl. I found Graph
module is quite helpful but it's not good enough. I want to create a
undirected graph,each node can connect each other with different
weights in the graph. I can set up the start ('a') and end ('e')
points,the routine should start from 'a' and pass every node,finish at
'e'. The script can find the shortest routine at last, for example
a->c->b->d->e. I can use APSP_Floyd_Warshall and
$SP->path_vertices('a','e') functions. But it will only return the
shortest way between 2 points, such as a->e,it doesn't pass and count
every node. Does anybody can help me?
Thank you very much.
David Meng
-------------------Start-----------
#!/usr/bin/perl -w
use strict;
use Graph::Undirected;
my $g = new Graph::Undirected->new;
$g->add_weighted_edge('a', 'b', 1);
$g->add_weighted_edge('a', 'c', 2);
$g->add_weighted_edge('a', 'd',3);
$g->add_weighted_edge('a', 'e',4);
$g->add_weighted_edge('b', 'c',5);
$g->add_weighted_edge('b', 'd',6);
$g->add_weighted_edge('b', 'e',7);
$g->add_weighted_edge('c', 'd',8);
$g->add_weighted_edge('c', 'e',9);
$g->add_weighted_edge('d', 'e',10);
my $SP = $g->APSP_Floyd_Warshall;
$path = $SP->path_length('a', 'e');
print " The shortest path from a to e is $path \n";
@pp= $SP->path_vertices('a','e');
print "path=@pp\n";
--------------END--------
output :
The shortest path from a to e is 4
path=a e
I'm designing a project to solve TSP issue with Perl. I found Graph
module is quite helpful but it's not good enough. I want to create a
undirected graph,each node can connect each other with different
weights in the graph. I can set up the start ('a') and end ('e')
points,the routine should start from 'a' and pass every node,finish at
'e'. The script can find the shortest routine at last, for example
a->c->b->d->e. I can use APSP_Floyd_Warshall and
$SP->path_vertices('a','e') functions. But it will only return the
shortest way between 2 points, such as a->e,it doesn't pass and count
every node. Does anybody can help me?
Thank you very much.
David Meng
-------------------Start-----------
#!/usr/bin/perl -w
use strict;
use Graph::Undirected;
my $g = new Graph::Undirected->new;
$g->add_weighted_edge('a', 'b', 1);
$g->add_weighted_edge('a', 'c', 2);
$g->add_weighted_edge('a', 'd',3);
$g->add_weighted_edge('a', 'e',4);
$g->add_weighted_edge('b', 'c',5);
$g->add_weighted_edge('b', 'd',6);
$g->add_weighted_edge('b', 'e',7);
$g->add_weighted_edge('c', 'd',8);
$g->add_weighted_edge('c', 'e',9);
$g->add_weighted_edge('d', 'e',10);
my $SP = $g->APSP_Floyd_Warshall;
$path = $SP->path_length('a', 'e');
print " The shortest path from a to e is $path \n";
@pp= $SP->path_vertices('a','e');
print "path=@pp\n";
--------------END--------
output :
The shortest path from a to e is 4
path=a e