Floyd-Warshall algorithm implementations


Two implementations of the Floyd-Warshall algorithm.

In recent post PWC118 - Adventure of Knight I gave a solution leveraging the Floyd-Warshall algorithm, which is an all-pairs shortest path algorithm for directed, weighted graphs (which means that it’s easily used in undirected non-weighted graphs too).

The all pairs part refers to the fact that the algorithm’s output is the shortest path across each possible pair of nodes in the graph (other ones, like Dijkstra’s algorithm, are so-called single source because they concentrate on the shortest path from a specific node to all othe others).

I did an implementation in Perl some time ago, available in cglib-perl. The fun part is that I mistakenly did this:

use PriorityQueue;

which I also copied into the code for the challenge, but the algorithm does not use a priority queue. Whatever, it’s now correct in FloydWarshall.pm.

More recently, I also added a porting of the implementation to Raku, as part of cglib-raku; the result is FloydWarshall.rakumod.

It has an object-oriented interface, which is probably better than the half-baked OO-ish solution that I chose (returning a few sub references to get the needed information), but overall it’s the same as the Perl module. Well, with the exception that in the Perl version you can pass one start node as a scalar or multiple starts nodes as an array reference, while in the Raku implementation you only get starts (pass one single item in case).

I hope they can be helpful!

Comments? Octodon, , GitHub, Reddit, or drop me a line!