ダイクストラ法

dijkstra.pl

#!/usr/bin/env perl

use strict;
use warnings;
use feature 'say';

use DDP { deparse => 1 };

my $graph = [];
for my $line (<DATA>){
    chomp($line);
    $line =~ s/\s+//g;
    my @data = split(/,/, $line);
    push @$graph, \@data;
}

my @sum;
my @from;
for (1..8){
    push @sum, -1;
    push @from, -1;
}

$sum[0] = 0;
my $snode;
my $enode;
while ($sum[7] == -1){
    my $min = 999999;
    for my $i (0..7){
        if ($sum[$i] != -1){
            for my $j (0..7){
                if ($sum[$j] == -1 && $graph->[$i]->[$j] > 0){
                    if ($sum[$i] + $graph->[$i]->[$j] < $min){
                        $min = $sum[$i] + $graph->[$i]->[$j];
                        $snode = $i;
                        $enode = $j;
                    }
                }
            }
        }
    }
    $sum[$enode] = $min;
    $from[$enode] = $snode;
}
say "$sum[7]";
my $pos = 7;
my @pos;
while ($pos != 0){
    $pos = $from[$pos];
    push @pos, $pos;
}
for my $p (reverse @pos){
    print "$p->"
}
print "7\n";

__DATA__
0, 200, 1000, 550, -1, -1, -1, -1
200, 0, -1, -1, 800, -1, -1,-1
1000, -1, 0, 120, -1, 250, 330, -1
550, -1, 120, 0, 300, -1, -1, 880
-1, 800, -1, 300, 0, -1, -1, 450
-1, -1, 250, -1, -1, -1, 120, -1
-1, -1, 330, -1, -1, 120, 0, 130
-1, -1, -1, 880, 450, -1, 130, 0