in reply to Graph modules

Implementing the Dijkstra algorithm is pretty trivial but Paths::Graph has a shortest path method that returns all the shortest paths if there are more than one. It is pure Perl so installation should not be an issue.

Replies are listed 'Best First'.
Re^2: Graph modules
by lima1 (Curate) on May 19, 2008 at 14:01 UTC
    Yes, but there are better solutions than running N * (N+1)/2 times Dijkstra... (google All Pairs Shortest Path Problem)

    I'd be surprised if the boost library has not all the required functionality. It's probably just not implemented in the Perl bindings. If speed is an issue, then maybe just use the C++ library directly, otherwise try Graph as suggested.

    Update: Graph also returns a "random" shortest graph.

[reply]
      Indeed, boost does have an implementation of the betweenness centrality measure. It might be the way to go, thanks
[reply]
Re^2: Graph modules
by nosbod (Scribe) on May 19, 2008 at 15:44 UTC
    ahha, thanks
[reply]

In Section Seekers of Perl Wisdom