Как я могу напечатать путь графа с таким количеством связей, используя dijkstram?

Question

У меня есть ненаправленный граф с 57 узлами и 204 связями. Я вычисляю кратчайший путь из всех узлов с его подузлами, используя алгоритм Дейкстрама, но я не смог распечатать путь узлов из данного корня. вот как я пытался.

########## the dijkstram algorithm#################
sub dijkstra {
    my ($graph, $root) = @_;
    my (%dist, %prev);

    foreach $n (keys %{$graph}) { $dist{$n} = inf; $prev{$n}=$n; }
    # .. except the source
    $dist{$root} = 0;

    # loop while we have unsolved nodes
    # sort unsolved by distance from root
    foreach my $n1 (sort keys %{$graph}) {
        foreach my $n2 (keys %{$graph->{$n1}}) {
            if (($dist{$n2} eq inf)) {
                $dist{$n2} = $dist{$n1} + $graph->{$n1}{$n2};
                $prev{$n2} = $n1;
            }
        }
    }
    return (\%prev, \%dist);
}
######## print the path and the distance for a given node#############
sub printPaths {
    my ($graph, $prev, $dist) = @_;
    my $path;

    foreach $n (keys %{$graph}) {
        my $t = $n;
        $path = $t;
        while ($t ne $root) {
            $t = $prev->{$t}; $path = "$t -> " . $path;
        }
        print "$n\t$dist->{$n}\t$path\n";
    }
}

проблема возникает в цикле while. когда он получает узел, у которого нет того же корня, и когда предыдущий узел всегда возвращает один и тот же узел. пожалуйста, помогите мне или дайте мне любое предложение. спасибо

Answer 1

Предостережение: у меня нет опыта работы с вашей проблемной областью, так что, возможно, это и не ответ. Однако это может дать некоторые указания относительно того, где могут возникнуть проблемы (надеюсь).

Я запустил ваш код со следующими данными в prot.ini:

ARR1 MafB
MafB JunD
ARR1 MET4
ARR1 ATF1
ARR1 BACH1
ARR1 CHOP 
ATF1 BACH1
ATF1 MET4
ATF1 NFE2L1
ATF2 ATF7
ATF2 BATF

(убрал гипс для удобочитаемости!)

после функции dijkstra% prev выглядит так:

$prev = {
          'ATF1' => 'ARR1',
          'MafB' => 'ARR1',
          'BACH1' => 'ARR1',
          'BATF' => 'ATF2',     # problem here
          'ATF2' => 'BATF',     # values are cyclic
          'CHOP' => 'ARR1',
          'ARR1' => 'ARR1',
          'JunD' => 'MafB',
          'NFE2L1' => 'ATF1',
          'ATF7' => 'ATF2',      
          'MET4' => 'ARR1'
        };

В вашем print_path цикл while $ t бесконечно чередуется между 'BATF' и 'ATF2'.

Вы можете обнаружить это в функции print_path - но в итоге я добавил следующую строку в функцию dijkstra, чтобы предотвратить циклические проблемы:

if (($dist{$node2} eq inf)) {
  $dist{$node2} = $dist{$node1} + $graph->{$node1}{$node2};
  if ($prev{$node1} ne $node2) {
    $prev{$node2} = $node1;
  }
}

затем я изменил цикл while в функции print_path:

while ($tmp ne $root) {
    $tmp = $prev->{$tmp};
    last unless $tmp;
    $path = "$tmp -> $path";
}

Также я заметил, что в этой строке:

$dist{$node2} = $dist{$node1} + $graph->{$node1}{$node2};

$ dist {$ node1} может быть бесконечностью, поэтому результатом будет бесконечность. Не уверен, что это намеренно.

Надеюсь, это поможет.