具体参考《算法图解》这本书第7章讲的，原书是用python写的，我用PHP再写一次，并稍加完善
把书上这三道练习题，拿来测试
网上再找了一个稍“难”点的题
上代码：
class ShortPath{
protected $graph=[];//只需要存每个节点所对应的邻居们，就能表示一个图了
protected $parents=[];//保存父级关系，最终能通过这个数组，回溯走过的最短路线
protected $costs;//从起点，到每个节点的花销
protected $infinity=999999;//用一个很大的数字，来代表一个正无穷大
protected $processed=[];//已处理过的节点的key
public function __construct($graph)
{
$this->graph=$graph;
//初始化父级数组， 即：只知道start的邻居，就是start的父级
foreach ($this->graph['start'] as $k=>$v) {
$this->parents[$k]='start';
}
//初始化花销数组，即：只知道start的邻居节点的花销，其它节点都是正无穷
foreach ($this->graph as $k=>$v) {
if($k=='start'){
$this->costs=$this->graph['start'];
}elseif(empty($this->costs[$k])){
$this->costs[$k]=$this->infinity;
}
}
$this->costs['finish']=$this->infinity;
}
public function find(){
$nodeKey=$this->findLowestCostNode($this->costs);
while ($nodeKey){//只要还有未处理过的节点
$cost=$this->costs[$nodeKey];
$neighbors=$this->graph[$nodeKey] ?? [];//取邻居
//遍历邻居
foreach ($neighbors as $k=> $v) {
$newCost=$cost+$v;
if($this->costs[$k] > $newCost){
$this->costs[$k]=$newCost;//将更低的开销更新
$this->parents[$k]=$nodeKey;
}
}
//调试输出
echo '当前节点：' .$nodeKey . PHP_EOL;
echo '邻居们:' . PHP_EOL;
print_r($neighbors);
echo '花销:' . PHP_EOL;
print_r($this->costs);
//既然已处理完了该节点的所有邻居，那么将该节点标记为已处理过了
$this->processed[]=$nodeKey;
//找出下一个待处理的节点
$nodeKey=$this->findLowestCostNode();
}
$this->showResult();
}
//在未处理过的节点中，查找出最短的那个
protected function findLowestCostNode(){
$lowestCost=$this->infinity;//在这里设置为正无穷是为了，在第一次进入循环时，必然比第一个元素大
$lowestCostKey=false;//要返回的最短路径节点的key
foreach ($this->costs as $k=>$v) {
if($v<$lowestCost && !in_array($k,$this->processed)){
$lowestCost=$v;
$lowestCostKey=$k;
}
}
return $lowestCostKey;
}
//美化显示处理结果
protected function showResult(){
$path=[];
$key='finish';
//从终点开始，查找父级，回溯出最短路线
while (isset($this->parents[$key])){
array_unshift($path,$key);
$key=$this->parents[$key];
}
echo '最短路径全长是:' . $this->costs['finish'] . PHP_EOL;
echo '路线是:start->' . implode('->',$path) . PHP_EOL;
}
}
//对应练习题A
$graph1=[
"start"=>[
"a"=>2,
"b"=>5,
],
"a"=>[
"b"=>8,
"d"=>7,
],
"b"=>[
"c"=>4,
"d"=>2,
],
"c"=>[
"finish"=>3,
"d"=>6
],
"d"=>[
"finish"=>1
]
];
//对应练习题B
$graph2=[
"start"=>[
"a"=>10,
],
"a"=>[
"c"=>20,
],
"b"=>[
"a"=>1,
],
"c"=>[
"b"=>1,
"finish"=>30,
],
];
//对应练习题C。这里能看出，该算法不适用于有负权边的情况
$graph3=[
"start"=>[
"a"=>2,
"b"=>2,
],
"a"=>[
"c"=>2,
"finish"=>2
],
"b"=>[
"a"=>2,
],
"c"=>[
"b"=>-100,
"finish"=>2,
],
];
//对应最后一题，将图中的v0，改为start，v8改为finish
$graph4=[
"start"=>[
"v1"=>1,
"v2"=>5,
],
"v1"=>[
"start"=>1,
"v2"=>3,
"v3"=>7,
"v4"=>5,
],
"v2"=>[
"start"=>5,
"v1"=>3,
"v4"=>1,
],
"v3"=>[
"v1"=>7,
"v2"=>2,
"v6"=>3,
],
"v4"=>[
"v1"=>5,
"v2"=>1,
"v3"=>2,
"v5"=>3,
"v6"=>6,
"v7"=>9,
],
"v5"=>[
"v2"=>6,
"v4"=>3,
"v7"=>5,
],
"v6"=>[
"v3"=>3,
"v4"=>6,
"v7"=>2,
"finish"=>7
],
"v7"=>[
"v4"=>9,
"v5"=>5,
"v6"=>2,
"finish"=>4
],
];
$obj=new ShortPath($graph4);
$obj->find();
最后一题的结果输出展示
最后附上《算法图解》这本书的pdf版
链接:https://pan.baidu.com/s/1Nditk7Waynn7c9FZ3ldnGw 密码:ij0r