in reply to OT(ish) - Best Search Algorithm
Maybe http://en.wikipedia.org/wiki/Dijkstra's_algorithm?
Seems to be implemented in Boost::Graph. Update: Sorry, haven't read the part you mentioned the A* algorithm :( .
In Section
Seekers of Perl Wisdom