#!/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
[download]

Abigail