#!/usr/bin/perl
# Ed Dijkstra's Shortest-Path, by pope
#
# Demonstrates practical uses of Infinity
# (http://www.perl.com/CPAN-local/doc/FMTEYEWTK/is_numeric.html).
# Feed a file consisting neighbourhood matrices like shown below to 
# this script:
#
#  0, 50, 10, 40, 45, ~
#  ~,  0, 15,  ~, 10, ~
# 20,  ~,  0, 15,  ~, ~
#  ~, 20,  ~,  0, 35, ~
#  ~,  ~,  ~, 30,  0, ~
#  ~,  ~,  ~,  3,  ~, 0
#
# Tilde is used to represent unavailable route (infinite distance in 
# mathematical sense).

use strict;
use vars qw(@m %state $FINISH $opt_s);
use Getopt::Std;

BEGIN { $FINISH = 0 }

sub sum {
    my $s;
    while (@_ > 1) { $s += $m[shift()]->[$_[0]] }
    $s;
}

sub output {
    my %s = @_;
    print "The shortest route from ", $opt_s, " to: \n";
    for (keys(%{$s{array}})) {
        print "$_ is: ", join(", ", @{$state{array}->{$_}->{r}}), 
            " with distance: ", $state{array}->{$_}->{d}, "\n";
    }       
}

# eat command line argument

getopts('s:');
defined(my $start = $opt_s) or die "Usage: $0 -s start_node matrices_file";

while (<>) { next if /^\s*$/;s/\s//g;s/~/Infinity/g;push @m, [split(/,\s*/, $_)] }

{
my ($cnt, $cnt1);
%state = (  node  => undef,
            track => undef,
            array => {map {$cnt++ => $_ } 
                      map { {s => 0, d => $_, r => [$start, $cnt1++]} } 
                      @{$m[$start]}} 
         );
}

my $loop = 0;

while (not $FINISH) {
    my ($cnt, $cnt1);

# select the unselected
    my @min = grep {/\d/}
           map {!$state{array}->{$_}->{s} ? $_ : undef} 
           sort { 
                my $aa = $state{array}->{$a}->{d};
                my $bb = $state{array}->{$b}->{d};
                $aa <=> $bb; 
                } 
           keys(%{$state{array}});

# set node, track and s 
    @state{'node','track'} = ($min[0], $state{array}->{$min[0]}->{r});
    $state{array}->{$min[0]}->{s} = 1;

# prepare the state for the next loop
    for (@min) {
        if ( (my $nd = sum(@{$state{track}}, $_)) < 
            $state{array}->{$_}->{d}) {
            $state{array}->{$_}->{d} = $nd;
            $state{array}->{$_}->{r} = [@{$state{track}}, $_];
        }
    }
    $FINISH = 1 if (++$loop >= @{$m[0]} ); 
}
output(%state);