Раздел «Алгоритмы».DijkstraAlgoPerl:

Реализация алгоритма Дейкстры на Perl

Формулировка задачи и теория

Этот код требует модуль Heap.pm с определением бинарной кучи (см. BinaryHeapPerl).

Использование бинарной кучи оправдано, если граф разряженный, например, степень вершин ограничена небольшим числом. Если же суммарное число рёбер порядка V*V, где V — число вершин, двоичную кучу лучше не использовать.

Данный код предполагает, что

Эти входные данные вы должны подготовить сами.

package Dijkstra;
use strict;
use Heap;

sub dijkstra {
   my $G = shift;
   my $src    = shift;

   my $H = queue_nodes($G, $src);      # Heap of nodes 
   my $u;
   while ( $u = $H->extract_min ) {   # Extract the closest node
      my $adjacent = $u->{"adjacent"}; # and 
      foreach my $e ( @$adjacent ) {
         update($H, $e, $u, getlength($e));      }
   }
}

sub update {
   my $H = shift;
   my $dest = shift;
   my $src = shift;
   my $len = shift;
   my $newlen;
   $newlen = getdist ($src) + $len;

   if ($newlen < getdist ($dest)) {
      $H->delete ($dest);
      setdist ($dest, $newlen);
      $H->insert ($dest);
   }
}

sub getlength {
   my $e = shift;
   return $e->{"len"}
}


sub getdist {
   my $n = shift;
   return $n->{"key"}
}

sub setdist {
   my $n = shift;
   my $dist = shift;
   $n->{"key"} = $dist;
}

sub queue_nodes {
   my ($G, $src) = shift;

   my $H = Heap->new;

   foreach my $n ( @{$G->{"nodes"}} ) {
      setdist ($n, 10E+100);
   }
   setdist ($src, 0);

   foreach my $n ( @{$G->{"nodes"}} ) {
      $H->insert ( $n );
   }
   return $H;

}
AlgorithmClasifyForm
Type: Код
Scope: Графы
Strategy:  
Language:  
Complexity: Medium