我有一个有57个节点和204个连杆的无向图。我使用Dijkstram算法计算所有节点及其子节点的最短路径,但我无法从给定的根打印节点的路径。以下是我的尝试。
########## 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 "$nt$dist->{$n}t$pathn";
}
}
问题发生在while循环中。当它得到一个不具有相同根的节点,并且前一个节点总是返回相同的节点时。请帮助我或给我任何建议。由于
警告:我在您的问题领域没有经验,所以这可能不是一个答案本身。然而,这我提供了一些指针,在哪里问题可能存在(希望)。
我在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;
}
}
然后修改了print_path函数中的while循环:
while ($tmp ne $root) {
$tmp = $prev->{$tmp};
last unless $tmp;
$path = "$tmp -> $path";
}
我还注意到在这一行中:
$dist{$node2} = $dist{$node1} + $graph->{$node1}{$node2};
$dist{$node1}可以是无穷大:所以结果仍然是无穷大。我不确定这是不是故意的。