単一ストリーム最短パス (ダイクストラ アルゴリズム) php 実装

単一ソースの最短パス (ダイクストラ アルゴリズム) PHP 実装
単一ソースの最短パス アルゴリズムが症例スコアリングに使用される医療プロジェクトを実行します。単一ソース最短経路のダイクストラ アルゴリズムの考え方は次のとおりです。
i から j への最短経路 (Vi...Vk, Vj) がある場合、 ＶｋはＶｊの前の頂点である。したがって、(Vi...Vk) も i から k への最短経路でなければなりません。ダイクストラは、最短経路の長さを増加させながら、最短経路を次々に生成するアルゴリズムです。たとえば、ソース頂点 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] はエッジを表すと仮定します。私はjにかかります。
1. V-U から dist[i] 値を最小にする頂点 i を選択し、i を U に追加します。

2. dist を更新します。直接隣接する頂点の値。 (dist[j]=min{dist[j],dist[i]+cost[i][j]})

3. U=V がわかったら停止します。

PHP の固有のプロパティを使用したコードは次のとおりです。

function dijkstra(){			$node_info_arr=array(	//结点的邻接表结构		array(			'node_id'=>0,		//某个结点的id			'next_node'=>array(4,2,1),			'node_type'=>0,			'cost'=>array(10,30,100)			),		array(			'node_id'=>4,		//某个结点的id			'next_node'=>array(3),			'node_type'=>1,			'cost'=>array(50)			),		array(			'node_id'=>3,		//某个结点的id			'next_node'=>array(1),			'node_type'=>1,			'cost'=>array(10)			),		array(			'node_id'=>2,		//某个结点的id			'next_node'=>array(3,1),			'node_type'=>1,			'cost'=>array(60,60)			),		array(			'node_id'=>1,		//某个结点的id			'next_node'=>array(),			'node_type'=>2,			'cost'=>array()			)	);		$start_node_id=false;		//起始结点id	$i_cost=array(array());	//两个节点之间的开销	$i_dist=array();		//起始点到各点的最短距离	$b_mark=array();		//是否加入了	foreach($node_info_arr as &$node_info){		if($node_info['node_type']==0){			$start_node_id=$node_info['node_id'];			//找到初始节点		}		foreach($node_info['next_node'] as $key=>$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<$node_count;$i++){		$min='INF';								//当前节点的最近距离		if(is_array($i_cost[$current_node_id])){			foreach($i_cost[$current_node_id] as $key=>$val){				if($i_dist[$key]=='INF'||$i_dist[$key]>$i_dist[$current_node_id]+$val){					$i_dist[$key]=$i_dist[$current_node_id]+$val;				}			}		}		foreach($i_dist as $key=>$val){			if(!$b_mark[$key]){				if($val!='INF'&&($min=='INF'||$min>$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=>$val){		echo $start_node_id.'=>'.$key.':'.$val.'<br />';	}}

例を示します。画像内:

実行結果は次のとおりです:
0=>0:0
0=>4:10
0=>3: 60
0=> ;2:30
0=>1:70

転載元：カンルイ族 ? >単一ソースの最短パス php 実装