81 lines
1.7 KiB
Raku
81 lines
1.7 KiB
Raku
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;
|