#!/usr/bin/perl
use strict;
use DBI;
my $dbh = DBI->connect( blah blah blah );
sub findpath {
my ($from, $to) = @_;
my $sth = $dbh->prepare( "select dest from tablename where src = ?" );
my %closed;
my @open;
# we start with the source node, a zero-length path
push @open, [ $from ];
while ( @open ) {
# sort by length, shortest at the top.
# note: this is much better implemented as a heap.
@open = sort { scalar(@$a) <=> scalar(@$b) } @open;
# $expand is the one we expand, it's the shortest.
# remove it from @open, and keep it.
my $expand = shift @open;
# query for what's connected to the last node in the list
$sth->execute($expand->[-1]);
# and add each of the result rows as a new path,
# the original path in $expand plus the new node.
while ( my $row = $sth->fetchrow_arrayref ) {
# skip the ones that we've closed (there are shorter paths already)
next if exists $closed{$row->[0]};
# close that node
$closed{$row->[0]} = 1;
# return the path if it goes where we want it to go.
return @$expand, $row->[0] if $row->[0] == $to;
# and add the appended path.
push @open, [ @$expand, $row->[0] ];
} # fetchrow
} # while @open
return undef; # no path to go from -> to.
}