From acbc804d0551bf986e37ab021335aa0cd0fb4608 Mon Sep 17 00:00:00 2001
From: doy <doy@tozt.net>
Date: Sun, 14 Dec 2008 17:31:25 -0500
Subject: dijkstra is just astar with a heuristic that always returns 0

---
 lib/Graph/Implicit.pm | 11 +++++++----
 1 file 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 {
 }
 
-- 
cgit v1.2.3-54-g00ecf