$realation = array();
$realation['you'] = array('alice', 'bob', 'claire');
$realation['alice'] = array('peggy');
$realation['bob'] = array('anuj', 'peggy');
$realation['claire'] = array('thom', 'jonny');

$realation['anuj'] = array();
$realation['peggy'] = array('you');
$realation['thom'] = array();
$realation['jonny'] = array();

$checkedList = array();

$search_queue = array();

function isSeller($name){
	if($name == 'jonny'){
		return true;
	}
	
	return false;
}

$search_queue = array_merge($search_queue, $realation['you']);

while(count($search_queue) > 0){
	$person = array_shift($search_queue);
	print_r("Check $person" . PHP_EOL);
	
	if(array_key_exists($person, $checkedList)){
		print_r("$person has checked! ignore!" . PHP_EOL);
		continue;
	}
	
	if(isSeller($person)){
		print_r("$person is a seller!" . PHP_EOL);
		break;
	}else{
		// 不是销售商,将他的朋友添加到队列
		print_r("$person is not a seller, add his friend to queue!" . PHP_EOL);
		$checkedList[$person] = 1;
		$search_queue = array_merge($search_queue, $realation[$person]);
	}
}

// 构建整体数据
$data = array();

$data['start']['a'] = 6;
$data['start']['b'] = 2;

$data['a']['final'] = 1;

$data['b']['a'] = 3;
$data['b']['final'] = 5;

$data['final'] = array();

// 构建成本数据并初始化初始节点
$costs = array();

$costs['start']['value'] = 0;
$costs['start']['parent'] = null;

function findLowestNode($costs){
	if(!is_array($costs) || count($costs) < 1){
		return null;
	}
	$lowEstKey = null;
	$lowEstVal = null;
	foreach ($costs as $key => $loop) {
		// 已经处理过的节点不再处理
		if(array_key_exists('deal', $loop)){
			continue;
		}
		// 终点节点不处理
		if($key == 'final'){
			continue;
		}
		// 找出最小值节点
		$val = $loop['value'];
		if($lowEstKey === null){
			$lowEstKey = $key;
			$lowEstVal = $val;
		}
		
		if($val < $lowEstVal){
			$lowEstKey = $key;
			$lowEstVal = $val;
		}
	}
	
	if($lowEstKey === null){
		return null;
	}
	return array($lowEstKey, $lowEstVal);
}

$nowLowest = findLowestNode($costs);

while ($nowLowest != null){
	list($nowLowestKey, $nowLowestVal) = $nowLowest;
	
	$neighbors = $data[$nowLowestKey];
	
	foreach ($neighbors as $key => $loop) {
		$newCost = $nowLowestVal + $loop;
		
		// 如果成本表中还没有该相邻节点,把当前节点加入到成本表
		if(!array_key_exists($key, $costs)){
			$costs[$key]['value'] = $newCost;
			$costs[$key]['parent'] = $nowLowestKey;
		}else{
			// 如果有更优方案.更新当前节点的父节点和成本
			if($newCost < $costs[$key]['value'] || $costs[$key]['value'] == null){
				$costs[$key]['value'] = $newCost;
				$costs[$key]['parent'] = $nowLowestKey;
			}
		}
	}
	//  标记为已处理
	$costs[$nowLowestKey]['deal'] = 1;
	// 再获得当前成本表中最低成本的节点
	$nowLowest = findLowestNode($costs);
}

$road = array();

$node = $costs['final'];
while($node['parent'] != 'start'){
	array_push($road, $node['parent']);
	$node = $costs[$node['parent']];
}
$road = array_reverse($road);
array_unshift($road, 'start');
array_push($road, 'final');

print_r($road);

// 构建整体数据
$data = array();

$data['start']['a'] = 5;
$data['start']['b'] = 2;

$data['a']['c'] = 4;
$data['a']['d'] = 2;

$data['b']['d'] = 7;
$data['b']['a'] = 8;

$data['c']['final'] = 3;
$data['c']['d'] = 6;

$data['d']['final'] = 1;

$data['final'] = array();

// 运算结果是 8
// start->a->d->final

// 构建整体数据
$data = array();

$data['start']['a'] = 10;

$data['a']['b'] = 20;

$data['b']['final'] = 30;
$data['b']['c'] = 1;

$data['c']['a'] = 1;

$data['final'] = array();
//运行结果是 60
// start->a->b->final

// 构建整体数据
$data = array();

$data['start']['a'] = 2;
$data['start']['b'] = 2;

$data['a']['c'] = 2;
$data['a']['final'] = 2;

$data['b']['a'] = 2;

$data['c']['b'] = -1;
$data['c']['final'] = 2;

$data['final'] = array();
// 运行结果是 4.但存在负边.要注意.结果可能不准
// start->a->final