#!/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

---

---

Posts are HTML formatted. Put <p> </p> tags around your paragraphs. Put <code> </code> tags around your code and data!

Titles consisting of a single word are discouraged, and in most cases are disallowed outright.

Read Where should I post X? if you're not absolutely sure you're posting in the right place.

Please read these before you post! —

• How do I compose an effective node title?
• How do I post a question effectively?
• Markup in the Monastery

Posts may use any of the Perl Monks Approved HTML tags:

a, abbr, b, big, blockquote, br, caption, center, col, colgroup, dd, del, details, div, dl, dt, em, font, h1, h2, h3, h4, h5, h6, hr, i, ins, li, ol, p, pre, readmore, small, span, spoiler, strike, strong, sub, summary, sup, table, tbody, td, tfoot, th, thead, tr, tt, u, ul, wbr

You may need to use entities for some characters, as follows. (Exception: Within code tags, you can put the characters literally.)

	For:		Use:
	&		&
	<		&lt;
	>		&gt;
	[		&#91;
	]		&#93;

Link using PerlMonks shortcuts! What shortcuts can I use for linking?

See Writeup Formatting Tips and other pages linked from there for more info.