加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

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】收集整理供大家参考研究

如果以上内容对您有帮助,欢迎收藏、点赞、推荐、分享。

(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读