Dijkstra's algorithm: Difference between revisions
m
→{{header|Perl}}: use True not '1', some additional fiddling
m (→{{header|REXX}}: added whitespace.) |
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: use True not '1', some additional fiddling) |
||
Line 3,671:
<lang perl>use strict;
use warnings;
use constant True => 1;
sub add_edge {
Line 3,685 ⟶ 3,686:
while ($i <= $j) {
my $k = int(($i + $j) / 2);
if ($a->[$k]{dist} >= $v->{dist}) { $j = $k - 1 }
else { $
}
splice @$a, $i, 0, $v;
Line 3,698 ⟶ 3,695:
my ($g, $a, $b) = @_;
for my $v (values %$g) {
$v->{dist} =
delete $v->{prev};
delete $v->{visited};
Line 3,705 ⟶ 3,702:
my $h = [];
push_priority($h, $g->{$a});
while (
my $v = shift @$h;
last if !$v
$v->{visited} =
for my $e (@{$v->{edges}}) {
my $u = $e->{vertex};
Line 3,721 ⟶ 3,718:
my $g = {};
add_edge($g,
(['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]);
my $v = $g->{e};
my @a;
while ($v) {
push @a, $v->{name};
$v = $v->{prev};
}
my $path = join
print "$g->{e}{dist} $path\n";</lang>
{{out}}
<pre>26 acde</pre>
| |||