Prim's algorithm with Perl

prim.pl

#!/usr/bin/perl

use strict;
#
# This program calculates MST(minimum spanning tree) using
# Prim's Algorithm
#
#
#  Input:  the graph below.
#  Output: minimum spanning tree


# for simplicity, Infinity is expressed as 999
my @W = (
    [  0,     1, 999,  1,   5 ],
    [  9,     0,   3,  2, 999 ],
    [ 999,  999,   0,  4, 999 ],
    [ 999,  999,   2,  0,   3 ],
    [   3,  999, 999, 999,  0 ],
);

print "Original weighted graph\n";
&printArray(\@W);
&prim(\@W);

sub printArray{
    my $D = shift;
    my $size = scalar @$D;
    for(my $a=0;$a<$size;$a++){
        for(my $b=0;$b<$size;$b++){
            printf "%4d", $D->[$a][$b];
        }
        print "\n";
    }
}

sub prim{

    my ($i,$total_cost);
    my (@visited, @cost, @pi);
    my $D = shift;
    my $size = scalar @$D;

    for($i=0; $i<$size ;$i++){
        $visited[$i] = 0;
        $cost[$i] = 999;
    }

    $cost[0] = 0;
    $pi[0] = -1;

    while(1){
        my $mincost = 999;
        my $u;

        # select node that has minimum weight
        for($i=0; $i<$size ;$i++){
            if($visited[$i] == 0 && 
                 $cost[$i] < $mincost ){
                 $mincost = $cost[$i];
                 $u = $i;
            }
        } 

        # all visited
        if($mincost == 999){
            print "total weight of MST is: ".$total_cost."\n";
            last;
        }else{
            $total_cost += $mincost;
        }
        $visited[$u] = 1;
        
        for($i=0; $i<$size ;$i++){
            if($visited[$i] || $D->[$u][$i] == 999 ){
                next;
            }
            if(0 < $D->[$u][$i] && $D->[$u][$i] < 999 &&
                                      $D->[$u][$i] < $cost[$i] ){
                $cost[$i] = $D->[$u][$i];        # set minimum weight from edge node
                $pi[$i] = $u;                    # set nearest node
            }
            
        }
        if($pi[$u] == -1){ 
            print "add first node:".($u+1)."\n";
        }else{
            print "edge added: e<".($u+1).",".($pi[$u]+1).">\n";
        }
    }
}