dijkstra的perl实现
发布时间:2020-12-15 21:10:02 所属栏目:大数据 来源:网络整理
导读:今天PHP站长网 52php.cn把收集自互联网的代码分享给大家,仅供参考。 use strict;my @path = ();my @lastpath = ();my $count;my $inputfile = "input";my $max = 1000;#read the file from inputsub readfile{open(FD,"i
以下代码由PHP站长网 52php.cn收集自互联网 现在PHP站长网小编把它分享给大家,仅供参考 use strict; my @path = (); my @lastpath = (); my $count; my $inputfile = "input"; my $max = 1000; #read the file from input sub readfile{ open(FD,"input") or die "not find file $inputfile"; foreach my $line (<FD>){ my @keys = split(";",$line); my @line = (); foreach my $key (@keys){ push(@line,$key); } push(@path,@line) } } #set every 0 to 1000 except i=j sub getpath{ readfile; $count = $#path + 1; for ( my $i = 0; $i < $count; $i++){ for ( my $j = 0; $j < $count; $j++){ if ( $i != $j && $path[$i][$j] == 0){ $path[$i][$j] = $max; } } } } #get dijkstra sub dijkstra{ getpath; my @shortpath = (); #stopre the shortest path my @visted = (); #mark whether the node had been visted my $startnode = shift; #mark the start node my @vistpath = (); #every shor path for ( my $i = 0; $i < $count; $i++){ $vistpath[$i] = "$startnode --> $i"; } $shortpath[$startnode] = 0; $visted[$startnode] = 0; for ( my $t = 1; $t < $count; $t++){ for ( my $t = 0; $t < $count; $t++ ){ print $path[$startnode][$t]," "; } print "#######n"; my $next = -1; my $min = 1000; for( my $i = 0; $i < $count; $i++){ if( !defined($visted[$i]) and $path[$startnode][$i] < $min){ $min = $path[$startnode][$i]; $next = $i; } } $shortpath[$next] = $min; $visted[$next] = 0; for ( my $j = 0; $j < $count; $j++){ if ( !defined($visted[$j]) and $path[$startnode][$next] + $path[$next][$j] < $path[$startnode][$j]){ $path[$startnode][$j] = $path[$startnode][$next] +$path[$next][$j]; $vistpath[$j] = " $vistpath[$next] --> $j"; } } } for (my $i =0; $i < $count; $i++){ print "from $startnode to $i' shortpath is $vistpath[$i],its length is $path[$startnode][$i]n"; } print "####################################################n"; } dijkstra(0); 以上内容由PHP站长网【52php.cn】收集整理供大家参考研究 如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |