登录  /  注册

单流最短路径(dijkstra算法)php实现

php中文网
发布: 2016-06-13 11:56:45
原创
1251人浏览过

单源最短路径(dijkstra算法)php实现
做一个医学项目,其中在病例评分时会用到单源最短路径的算法。单源最短路径的dijkstra算法的思路如下:
如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。Dijkstra是以最短路径长度递增,逐次生成最短路径的算法。例如:对于源顶点V0,首先选择其直接相邻的顶点中长度最短的顶点Vi,那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+cost[i][j]}。假设G=,源点为V0,U={V0}表示已经标记过的顶点集合,dist[i]记录V0到i的最短距离,cost[i][j]表示边i到j的开销。   
1.从V-U中选择使dist[i]值最小的顶点i,将i加入到U中;

2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+cost[i][j]})

3.知道U=V,停止。

利用php特有的性质,其代码如下:

function dijkstra(){			$node_info_arr=array(	//结点的邻接表结构		array(			'node_id'=&gt;0,		//某个结点的id			'next_node'=&gt;array(4,2,1),			'node_type'=&gt;0,			'cost'=&gt;array(10,30,100)			),		array(			'node_id'=&gt;4,		//某个结点的id			'next_node'=&gt;array(3),			'node_type'=&gt;1,			'cost'=&gt;array(50)			),		array(			'node_id'=&gt;3,		//某个结点的id			'next_node'=&gt;array(1),			'node_type'=&gt;1,			'cost'=&gt;array(10)			),		array(			'node_id'=&gt;2,		//某个结点的id			'next_node'=&gt;array(3,1),			'node_type'=&gt;1,			'cost'=&gt;array(60,60)			),		array(			'node_id'=&gt;1,		//某个结点的id			'next_node'=&gt;array(),			'node_type'=&gt;2,			'cost'=&gt;array()			)	);		$start_node_id=false;		//起始结点id	$i_cost=array(array());	//两个节点之间的开销	$i_dist=array();		//起始点到各点的最短距离	$b_mark=array();		//是否加入了	foreach($node_info_arr as &amp;$node_info){		if($node_info['node_type']==0){			$start_node_id=$node_info['node_id'];			//找到初始节点		}		foreach($node_info['next_node'] as $key=&gt;$next_node){			$i_cost[$node_info['node_id']][$next_node]=$node_info['cost'][$key];		}		$i_dist[$node_info['node_id']]='INF';				//初始化为无穷大		$b_mark[$node_info['node_id']]=false;				//初始化未加入	}	if($start_node_id===false){		return '302';	}	//计算初始结点到各节点的最短路径	$i_dist[$start_node_id]=0;	//初始点到其本身的距离为0	$b_mark[$start_node_id]=true;	//初始点加入集合		$current_node_id=$start_node_id;	//最近加入的节点id	$node_count=count($node_info_arr);	for($i=0;$i$val){				if($i_dist[$key]=='INF'||$i_dist[$key]&gt;$i_dist[$current_node_id]+$val){					$i_dist[$key]=$i_dist[$current_node_id]+$val;				}			}		}		foreach($i_dist as $key=&gt;$val){			if(!$b_mark[$key]){				if($val!='INF'&amp;&amp;($min=='INF'||$min&gt;$val)){					$min=$val;					$candidate_node_id=$key;	//候选最近结点id				}			}		}		if($min=='INF'){			break;		}		$current_node_id=$candidate_node_id;		$b_mark[$current_node_id]=true;	}	foreach($i_dist as $key=&gt;$val){		echo $start_node_id.'=&gt;'.$key.':'.$val.'<br>';	}}
登录后复制

 其中例子为图:
    
运行结果为:
    0=>0:0
    0=>4:10
    0=>3:60
    0=>2:30
    0=>1:70


转自:康瑞的部落 ? 单源最短路径php实现


智能AI问答
PHP中文网智能助手能迅速回答你的编程问题,提供实时的代码和解决方案,帮助你解决各种难题。不仅如此,它还能提供编程资源和学习指导,帮助你快速提升编程技能。无论你是初学者还是专业人士,AI智能助手都能成为你的可靠助手,助力你在编程领域取得更大的成就。
来源:php中文网
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
最新问题
热门教程
更多>
最新下载
更多>
网站特效
网站源码
网站素材
前端模板
关于我们 免责申明 意见反馈 讲师合作 广告合作 最新更新
php中文网:公益在线php培训,帮助PHP学习者快速成长!
关注服务号 技术交流群
PHP中文网订阅号
每天精选资源文章推送
PHP中文网APP
随时随地碎片化学习
PHP中文网抖音号
发现有趣的

Copyright 2014-2024 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号