diff options
author | doy <doy@tozt.net> | 2008-12-14 17:31:25 -0500 |
---|---|---|
committer | doy <doy@tozt.net> | 2008-12-14 17:31:25 -0500 |
commit | acbc804d0551bf986e37ab021335aa0cd0fb4608 (patch) | |
tree | 58d368afa8d365927dd12e6818c4417f6f364e2e | |
parent | 63f7f895888b0bde7c60f1d5cd18399acec161f2 (diff) | |
download | graph-implicit-acbc804d0551bf986e37ab021335aa0cd0fb4608.tar.gz graph-implicit-acbc804d0551bf986e37ab021335aa0cd0fb4608.zip |
dijkstra is just astar with a heuristic that always returns 0
-rw-r--r-- | lib/Graph/Implicit.pm | 11 |
1 files changed, 7 insertions, 4 deletions
diff --git a/lib/Graph/Implicit.pm b/lib/Graph/Implicit.pm index 828c67f..2fad054 100644 --- a/lib/Graph/Implicit.pm +++ b/lib/Graph/Implicit.pm @@ -60,6 +60,12 @@ sub kruskal { sub dijkstra { my $self = shift; my ($from, $scorer) = @_; + return $self->astar($from, sub { 0 }, $scorer); +} + +sub astar { + my $self = shift; + my ($from, $heuristic, $scorer) = @_; my $pq = Heap::Simple->new(elements => "Any"); my %neighbors; @@ -80,7 +86,7 @@ sub dijkstra { unless exists $neighbors{$vertex}; for my $neighbor (@{ $neighbors{$vertex} }) { my ($vert_n, $weight_n) = @{ $neighbor }; - my $dist = $cost + $weight_n; + my $dist = $cost + $weight_n + $heuristic->($vertex, $vert_n); if (!defined $dist{$vert_n} || $dist < $dist{$vert_n}) { $dist{$vert_n} = $dist; $pred{$vert_n} = $vertex; @@ -91,9 +97,6 @@ sub dijkstra { return \%pred, $max_vert; } -sub astar { -} - sub bellman_ford { } |