Dijkstra's algorithm
class Graph {
has (%.edges, %.nodes);
method new(*@args){
my (%edges, %nodes);
for @args {
%edges{.[0] ~ .[1]} = $_;
%nodes{.[0]}.push( .[0] ~ .[1] );
%nodes{.[1]}.push( .[0] ~ .[1] );
}
self.bless(edges => %edges, nodes => %nodes);
}
method neighbours ($source) {
my (%neighbours, $edges);
$edges = self.nodes{$source};
for @$edges -> $x {
for self.edges{$x}[0..1] -> $y {
if $y ne $source {
%neighbours{$y} = self.edges{$x}
}
}
}
return %neighbours
}
method dijkstra ($source, $dest) {
my (%node_data, $v, $u);
my @q = self.nodes.keys;
for self.nodes.keys {
%node_data{$_}{'dist'} = Inf;
%node_data{$_}{'prev'} = '';
}
%node_data{$source}{'dist'} = 0;
while @q {
# %node_data.perl.say;
my ($mindist, $idx) =
@((map {[%node_data{@q[$_]}{'dist'},$_]},^@q).min(*[0]));
$u = @q[$idx];
if $mindist eq Inf {
return ()
}
elsif $u eq $dest {
my @s;
while %node_data{$u}{'prev'} {
@s.unshift($u);
$u = %node_data{$u}{'prev'}
}
@s.unshift($source);
return @s;
}
else {
@q.splice($idx,1);
}
for self.neighbours($u).kv -> $v, $edge {
my $alt = %node_data{$u}{'dist'} + $edge[2];
if $alt < %node_data{$v}{'dist'} {
%node_data{$v}{'dist'} = $alt;
%node_data{$v}{'prev'} = $u
}
}
}
}
}
my $a = Graph.new([
["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('a', 'e').say;
Output:
[a c f e]
Last updated