使用php完成最短路径查找

数据结构如图所示：

<?php$list=[ ???‘a‘=>[‘b‘=>1,‘c‘=>2,‘d‘=>3,], ???‘b‘=>[‘a‘=>1,‘c‘=>4,‘e‘=>9], ???‘c‘=>[‘a‘=>2,‘b‘=>4,‘d‘=>5,‘e‘=>6], ???‘d‘=>[‘a‘=>3,‘c‘=>5,‘e‘=>8], ???‘e‘=>[‘b‘=>7,‘c‘=>6,‘d‘=>8],];/*三要点：第一，初始化二个数组，一个存放已找到的最近节点，目的是防止重复寻找(如数组中已有a和b,下次从b就不用重复从b到a)，另一个存放除最近节点外所有与a连接的节点距离(存放c和d)。第二，从a出发，找到和a最近的节点b。第三，从这个最近的节点b出发，找出与这个节点最近的节点c，将这个通过b找到的节点c到a的距离与所有其它节点到a的距离比较。最后，重复三个步骤即可完成全部查找。最终数组：Array ( [0] => Array ( [b] => 0 [ba] => 1 [bac] => 3 [bad] => 4 [be] => 9 [bace] => 9 [bade] => 12 ) )*/function find($node,$list,$next,$a=[]){ ???????if(count($next)==count($list)){ ???????return $_GET=[array_merge($next,$a)]; ???} ????????foreach($list[$node[strlen($node)-1]] as $k=>$v){ ???????foreach($next as $n=>$m){ ???????????if($k==$n[strlen($n)-1]){ ???????????????unset($list[$node][$k]); ???????????} ???????????} ???} ???foreach($list[$node[strlen($node)-1]] as $k=>$v){ ???????????$a[$node.$k]=$next[$node]+$v; ???????} ???foreach($a as $k=>$v){ ???????foreach($next as $n=>$m){ ???????????if($k[strlen($k)-1]==$n[strlen($n)-1]){ ???????????????unset($a[$k]); ???????????} ???????} ???????} ???foreach($a as $k=>$v){ ???????if(!isset($smallest) || $smallest>$v ){ ???????????$smallest=$v ; ???????????$node=$k ; ???????} ???????} ???????????//$node=$node[strlen($node)-1]; ???$next[$node]=$smallest; ?????unset($smallest); ???????find($node,$list,$next,$a);}find(‘b‘,$list,[‘b‘=>0]); ????print_r($_GET);