0: #!/usr/bin/perl
1: # Ed Dijkstra's Shortest-Path, by pope
2: #
3: # Demonstrates practical uses of Infinity
4: # (http://www.perl.com/CPAN-local/doc/FMTEYEWTK/is_numeric.html).
5: # Feed a file consisting neighbourhood matrices like shown below to 
6: # this script:
7: #
8: #  0, 50, 10, 40, 45, ~
9: #  ~,  0, 15,  ~, 10, ~
10: # 20,  ~,  0, 15,  ~, ~
11: #  ~, 20,  ~,  0, 35, ~
12: #  ~,  ~,  ~, 30,  0, ~
13: #  ~,  ~,  ~,  3,  ~, 0
14: #
15: # Tilde is used to represent unavailable route (infinite distance in 
16: # mathematical sense).
17: 
18: use strict;
19: use vars qw(@m %state $FINISH $opt_s);
20: use Getopt::Std;
21: 
22: BEGIN { $FINISH = 0 }
23: 
24: sub sum {
25:     my $s;
26:     while (@_ > 1) { $s += $m[shift()]->[$_[0]] }
27:     $s;
28: }
29: 
30: sub output {
31:     my %s = @_;
32:     print "The shortest route from ", $opt_s, " to: \n";
33:     for (keys(%{$s{array}})) {
34:         print "$_ is: ", join(", ", @{$state{array}->{$_}->{r}}), 
35:             " with distance: ", $state{array}->{$_}->{d}, "\n";
36:     }       
37: }
38: 
39: # eat command line argument
40: 
41: getopts('s:');
42: defined(my $start = $opt_s) or die "Usage: $0 -s start_node matrices_file";
43: 
44: while (<>) { next if /^\s*$/;s/\s//g;s/~/Infinity/g;push @m, [split(/,\s*/, $_)] }
45: 
46: {
47: my ($cnt, $cnt1);
48: %state = (  node  => undef,
49:             track => undef,
50:             array => {map {$cnt++ => $_ } 
51:                       map { {s => 0, d => $_, r => [$start, $cnt1++]} } 
52:                       @{$m[$start]}} 
53:          );
54: }
55: 
56: my $loop = 0;
57: 
58: while (not $FINISH) {
59:     my ($cnt, $cnt1);
60: 
61: # select the unselected
62:     my @min = grep {/\d/}
63:            map {!$state{array}->{$_}->{s} ? $_ : undef} 
64:            sort { 
65:                 my $aa = $state{array}->{$a}->{d};
66:                 my $bb = $state{array}->{$b}->{d};
67:                 $aa <=> $bb; 
68:                 } 
69:            keys(%{$state{array}});
70: 
71: # set node, track and s 
72:     @state{'node','track'} = ($min[0], $state{array}->{$min[0]}->{r});
73:     $state{array}->{$min[0]}->{s} = 1;
74: 
75: # prepare the state for the next loop
76:     for (@min) {
77:         if ( (my $nd = sum(@{$state{track}}, $_)) < 
78:             $state{array}->{$_}->{d}) {
79:             $state{array}->{$_}->{d} = $nd;
80:             $state{array}->{$_}->{r} = [@{$state{track}}, $_];
81:         }
82:     }
83:     $FINISH = 1 if (++$loop >= @{$m[0]} ); 
84: }
85: output(%state);