我的dijkstra算法在perl中用来对等权重的图进行反定向，有什么问题吗？它不会停止迭代

Question

我有一个蛋白质节点的加权图。我正在编写一个Perl程序，使用Dijkstra算法查找给定节点的最短路径。每个蛋白质(顶点)具有相同的重量。我的程序不会停止迭代，也不会给我任何输出。我不知道是什么导致了这个问题。

我的想法是从用户那里获取蛋白质节点的名称，并使用给定的蛋白质作为根节点来开始搜索最短路径。

%graph = (
  'A' => {'B' => 1, 'C' => 5},
  'B' => {'C' => 4, 'D' => 2},
  'C' => {'A' => 1, 'B' => 3},
  'D' => {'C' => 2, 'B' => 3}
);

sub dijkstra {
    print "Enter a node\n";
    my $root= <>;
    my $infinity = "inf";
    my %graph= %graph;
    my %dist;
    my %prev;
    ############################ the algorithm ####
    # first, set all distances to infinity
    foreach $n (keys %graph) { $dist{$n} = $infinity; $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 $infinity) ||
                ($dist{$n2} > ($dist{$n1} + $graph{$n1}{$n2}) )) {
                $dist{$n2} = $dist{$n} + $graph{$n1}{$n2};
                $prev{$n2} = $n1;
            }
        }
    }
    ##### print the solutions ######
    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";
    }
}
dijkstra();

Answer 1

当您使用<>读取输入时，它包含尾随的换行符。因此，它不等于%graph中的任何键(假定没有换行符)。快速解决方法是对根目录执行chomp。

...
my $root = <>;
chomp $root;

完整的修复方法是检查$root是否为有效顶点，如果不是，则输出错误。请注意，您不应该在同一函数中处理用户输入和应用程序逻辑。减少coupling的Separate concerns。

还有，globals are bad。如果您正在做的话，包变量并不是那么糟糕，但是应该将%group传递给dijkstra (作为reference)，这样实现就不会与图形紧密相关。将图形作为参数传递会使代码变得更紧凑。

请注意，您不需要定义自己的无穷大。Perl有inf (和-inf)。

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

    ############################ the algorithm ####
    # first, set all distances to infinity
    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}) )) {
                $dist{$n2} = $dist{$n} + $graph->{$n1}{$n2};
                $prev{$n2} = $n1;
            }
        }
    }
    return (\%prev, \%dist);
}

sub getNode {
    my $graph = shift;
    print "Enter a node\n";
    my $root= <>;
    chomp $root;
    if (! exists $graph->{$root}) {
        die("'$root' isn't a valid node.\n");
    }
    return $root;
}

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";
    }
}

$graph = {
  'A' => {'B' => 1, 'C' => 5},
  'B' => {'C' => 4, 'D' => 2},
  'C' => {'A' => 1, 'B' => 3},
  'D' => {'C' => 2, 'B' => 3}
};
$root = getNode($graph);
#($prev, $dist) = dijkstra(\%graph, $root);
#printPaths($graph, $prev, $dist);
# or, for obfuscation:
printPaths($graph, dijkstra($graph, $root));

要调试这样的东西，可以使用脚手架(在代码中的不同位置打印调试消息；Data::Dumper对此很有用)。更好的是，学习使用interactive debugger。