64 lines
1.5 KiB
Perl
64 lines
1.5 KiB
Perl
use strict;
|
|
use warnings;
|
|
use constant True => 1;
|
|
|
|
sub add_edge {
|
|
my ($g, $a, $b, $weight) = @_;
|
|
$g->{$a} ||= {name => $a};
|
|
$g->{$b} ||= {name => $b};
|
|
push @{$g->{$a}{edges}}, {weight => $weight, vertex => $g->{$b}};
|
|
}
|
|
|
|
sub push_priority {
|
|
my ($a, $v) = @_;
|
|
my $i = 0;
|
|
my $j = $#{$a};
|
|
while ($i <= $j) {
|
|
my $k = int(($i + $j) / 2);
|
|
if ($a->[$k]{dist} >= $v->{dist}) { $j = $k - 1 }
|
|
else { $i = $k + 1 }
|
|
}
|
|
splice @$a, $i, 0, $v;
|
|
}
|
|
|
|
sub dijkstra {
|
|
my ($g, $a, $b) = @_;
|
|
for my $v (values %$g) {
|
|
$v->{dist} = 10e7; # arbitrary large value
|
|
delete @$v{'prev', 'visited'}
|
|
}
|
|
$g->{$a}{dist} = 0;
|
|
my $h = [];
|
|
push_priority($h, $g->{$a});
|
|
while () {
|
|
my $v = shift @$h;
|
|
last if !$v or $v->{name} eq $b;
|
|
$v->{visited} = True;
|
|
for my $e (@{$v->{edges}}) {
|
|
my $u = $e->{vertex};
|
|
if (!$u->{visited} && $v->{dist} + $e->{weight} <= $u->{dist}) {
|
|
$u->{prev} = $v;
|
|
$u->{dist} = $v->{dist} + $e->{weight};
|
|
push_priority($h, $u);
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
my $g = {};
|
|
add_edge($g, @$_) for
|
|
(['a', 'b', 7], ['a', 'c', 9], ['a', 'f', 14],
|
|
['b', 'c', 10], ['b', 'd', 15], ['c', 'd', 11],
|
|
['c', 'f', 2], ['d', 'e', 6], ['e', 'f', 9]);
|
|
|
|
dijkstra($g, 'a', 'e');
|
|
|
|
my $v = $g->{e};
|
|
my @a;
|
|
while ($v) {
|
|
push @a, $v->{name};
|
|
$v = $v->{prev};
|
|
}
|
|
my $path = join '', reverse @a;
|
|
print "$g->{e}{dist} $path\n";
|