Skip to content

Instantly share code, notes, and snippets.

@tomcha
Created April 13, 2019 01:36
Show Gist options
  • Save tomcha/6a1561fa3dd84e7901997d2da28ae46f to your computer and use it in GitHub Desktop.
Save tomcha/6a1561fa3dd84e7901997d2da28ae46f to your computer and use it in GitHub Desktop.
ダイクストラ法
#!/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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment