Boost::Graph is well-documented and very easy to use.
Unfortunately, when I tried to determine the Dijkstra shortest path for a dataset of several hundred points with unevenly weighted paths, the memory usage would sometimes balloon like crazy. I'm fairly certain this is a property of the underlying Boost library, rather than this Perl interface.
When I switched from using Boost::Graph to the pure-Perl Graph module, my application stopped using up all the memory on the system, and my batch process ran about 10x faster. (It's quite possible that this issue is specific to my particular dataset.) It's too bad, because I like the interface to Boost::Graph better.