[Bioperl-l] OT: Breadth-First Search Algorithm - BFS
Jeremy Semeiks
jrs at denny.farviolet.com
Fri Feb 27 15:27:10 EST 2004
On Fri, Feb 27, 2004 at 04:55:21AM +0100, Jose M? Glez Izarzugaza wrote:
> Hello everyone,
>
> I'm working with a graph and I need to calculate the values of C and L, to do so, I need an algorithm to calculate the distance to the other elements.
>
> A good one is BFS algorithm.
>
> I tried to write the script (the algorithm itself) in Perl but I got absolutely lost.
>
> Can anyone help me?
Hi Jose,
One solution is to use the Graph::Base module on CPAN:
http://search.cpan.org/~jhi/Graph-0.20101/lib/Graph/Base.pm
This module includes Dijkstra's shortest path algorithm. Dijkstra's is
a few times slower than BFS, but you shouldn't see a difference for
small graphs. (And in my experience, if you're trying to run search
algorithms on large graphs, Perl is too slow anyway -- consider
something like the C++ Boost Graph library instead.)
HTH,
Jeremy
More information about the Bioperl-l
mailing list