Re: floyd warshall trans closure

I don't think the Floyd Warshall algorithm gives you a quick answer to this problem, and I'm pretty sure the implementation on Algorithm::Graphs::Transitive_Closure isn't going to give you that answer.

The algorithm to use to find the (shortest) path from one node in a graph to another node is Dijkstra's algorithm, which is linear in the number of edges in the graph. Floyd Warshall is cubic in the number of vertices, and solves the connectivity problem for all pairs of nodes at once.

I presume the Graph module on CPAN has a method for applying Dijkstra's algorithm.

Abigail

Comment on Re: floyd warshall trans closure

Replies are listed 'Best First'.
Re: Re: floyd warshall trans closure by Anonymous Monk on Oct 21, 2003 at 15:18 UTC
Thank you Abigail and hello other monks, I think I will try to go from scratch. I want to build a matrix using a hash of hashes so that I can delete items easily afterwards without the matrix getting illformed. I find it hard to use the packages, because they require a certain input format. But I'm wondering now... can I do multiplication with a matrix that is built as a hash of hashes? -Choco	[reply]
Re: floyd warshall trans closure by Abigail-II (Bishop) on Oct 21, 2003 at 15:54 UTC
I want to build a matrix using a hash of hashes so that I can delete items easily afterwards without the matrix getting illformed. I find it hard to use the packages, because they require a certain input format. I find this remark curious as the floyd_warshall sub can take a reference to a hash of hashes as argument. can I do multiplication with a matrix that is built as a hash of hashes? Sure, but you probably have to code it yourself. Abigail	[reply]
Re: Re: floyd warshall trans closure by Anonymous Monk on Oct 22, 2003 at 09:56 UTC
Hi Abigail and hello other monks Abigail said: "I find this remark curious as the floyd_warshall sub can take a reference to a hash of hashes as argument." as a response to my remark: "I want to build a matrix using a hash of hashes so that I can delete items easily afterwards without the matrix getting illformed." Exactly! And that's why I wanted to use the floyd_warshall sub so much!! The alternatives don't give me that freedom. The problem was just getting the number of paths. I am going to take a look at the re: that followed now. -Choco	[reply]