ETOOBUSY 🚀 minimal blogging for the impatient
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).
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!