| Subject: | Dijkstra heap logic |
The shortest path between A & B in the attached example is A-A1-L1-B1-B c/o setting the B2-B link higher than B1-B ( 2 vs 1 ).
Results of code attached gives:
A-A1,A-A2,A1-L1,A2-L2,B2-B,L1-B1,L2-B2 , ie via B2
If I read the code correctly , the wrong weight is being popped onto the fibonacci heap in _SPT_add , the weight of the link rather than the cumulative weight to the root ( $etc ? )
use Graph::Directed ;
my $g = Graph::Directed->new() ;
$g->add_weighted_edge('A', 'A1', 1) ;
$g->add_weighted_edge('A', 'A2', 1) ;
$g->add_weighted_edge('A1', 'A2', 1) ;
$g->add_weighted_edge('A2', 'A1', 1) ;
$g->add_weighted_edge('A1', 'L1', 100) ;
$g->add_weighted_edge('A2', 'L2', 100) ;
$g->add_weighted_edge('L1', 'B1', 100) ;
$g->add_weighted_edge('L2', 'B2', 100) ;
$g->add_weighted_edge('B1', 'B', 1) ;
$g->add_weighted_edge('B2', 'B', 2) ;
$g->add_weighted_edge('B1', 'B2', 1) ;
$g->add_weighted_edge('B2', 'B1', 1) ;
my $SSSP = $g->SPT_Dijkstra(first_root=>'A') ;
print $SSSP ;