#!/usr/bin/perl
use strict;
use warnings;
no warnings qw /syntax/;
sub min {
my $min;
map {$min = $_ if defined ($_) && (!defined ($min) || $_ < $min)}
+@_;
$min;
}
sub add {
my $sum = 0;
map {$sum += $_ // return} @_; # Defined-or!
$sum
}
sub display {
my $graph = shift;
my $count = @{$graph};
# Print top line.
print " |";
printf " %3d" => $_ for 1 .. $count;
print "\n";
print "----+", "-" x ($count * 4), "\n";
foreach my $x (1 .. $count) {
printf "%3d |", $x;
foreach my $y (1 .. $count) {
my $val = $graph -> [$x - 1] [$y - 1];
defined ($val) ? printf " %3d" => $val : print " Inf";
}
print "\n";
}
}
# Takes a ref to an array of arrays as argument. $ref -> [$x] [$y] is
# the weigth of the edge from $x to $y. This should be 0 if $x == $y,
# and undef if there's no edge from $x to $y. Negative weigths are
# possible, as long as there are no cycles with a negative length.
# The passed datastructure will be *modified*; the resulting array
# will contain the lengths of the shortest path - an undefined value
# will indicate there's no path.
# To find the number of edges that need to be taken, give all edges
# a weigth of 1.
sub floyd_warshall ($) {
my $graph = shift;
my $count = @{$graph};
for (my $k = 0; $k < $count; $k ++) {
for (my $i = 0; $i < $count; $i ++) {
for (my $j = 0; $j < $count; $j ++) {
$graph -> [$i] [$j] = min $graph -> [$i] [$j],
add $graph -> [$k] [$j],
$graph -> [$i] [$k];
}
}
}
$graph;
}
my $graph1 = [[ 0, undef, undef, undef],
[undef, 0, 1, 1],
[undef, 1, 0, undef],
[ 1, undef, 1, 0]];
my $graph2 = [[ 0, 3, 8, undef, -4],
[undef, 0, undef, 1, 7],
[undef, 4, 0, undef, undef],
[ 2, undef, -5, 0, undef],
[undef, undef, undef, 6, 0]];
floyd_warshall $graph1;
floyd_warshall $graph2;
display $graph1;
print "\n";
display $graph2;
__END__
| 1 2 3 4
----+----------------
1 | 0 Inf Inf Inf
2 | 2 0 1 1
3 | 3 1 0 2
4 | 1 2 1 0
| 1 2 3 4 5
----+--------------------
1 | 0 1 -3 2 -4
2 | 3 0 -4 1 -1
3 | 7 4 0 5 3
4 | 2 -1 -5 0 -2
5 | 8 5 1 6 0
Abigail |