The Graph::Directed module allows one to easily set up directed graphs and contains Dijkstra's algorithm for shortest paths.

To understand what is going on under the hood, look at the chapter on graphs in the book "Mastering Algorithms in Perl" published by O'Reilly.

-Mark