Dijkstra's algorithm: Difference between revisions

=={{header|Perl 6}}==

<lang perl6>

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;

</lang>

{{out}}

<pre>

a c f e</pre>