狄克斯特拉(Dijkstra) 算法 php实现

本文主要是介绍狄克斯特拉(Dijkstra) 算法 php实现，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

《算法图解》中提到的狄克斯特拉算法，用php实现。

一 原理及解释

根据示例图求出起点到终点的最小耗费路径。

因为涉及每条路径的权重，所以这种算法仅适合有向路径。

所谓有向路径，指仅从起点指向终点的路径。

相对的无向路径，指起点和终点互相指向的路径，一般这样的路径不带箭头。

该算法设定每条路径没有权重为负的路径，且没有不可指向终点的路径，所以所有节点都有效。

起点“O”，终点“C”，实例图如下

根据图示，路径0到A耗费1总耗费1记作A<-O:1:1，以此类推B<-O:2:1,选取耗费最小的路径A<-O:1:1，此时O节点遍历完成。

从节点A再次开始C->A:4,总耗费需要加上之前路径的耗费所以C->A:4:5，A节点遍历完成。

剩余B节点未处理，选取B节点开始C->B:1:3,B节点遍历完成。因为总消耗3小于总消耗5，所以选择C->B路径。

因为C节点是终点，不用便利。所以其余节点遍历完成，则C节点处理完成。

最终选择路径O->B->C,总消耗3。

二 处理流程

1、初始化

节点	总耗费	父节点	遍历完成
O	FALSE	FALSE	FALSE
A	FALSE	FALSE	FALSE
B	FALSE	FALSE	FALSE
C	FALSE	FALSE	FALSE

2、选取起点节点O

节点	总耗费	父节点	遍历完成
O	FALSE	FALSE	TRUE
A	1	O	FALSE
B	2	O	FALSE
C	FALSE	FALSE	FALSE

下一步，选取耗费最少且未遍历完成的节点，但是要注意耗费的值不能是FALSE。可将耗费中FALSE视为最大。

某些语言中有无穷大的常量关键字，可以直接用大小对比排除未设置耗费数量的节点。

3、选取节点A

节点	总耗费	父节点	遍历完成
O	FALSE	FALSE	TRUE
A	1	O	TRUE
B	2	O	FALSE
C	4	A	FALSE

B->A:3:4，原有节点总耗费为2,小于4。所以不采用B->A，即B->A的数据不更新到表中。

下一步，选取耗费最少且未遍历完成的节点。

4、选取节点B

节点	总耗费	父节点	遍历完成
O	FALSE	FALSE	TRUE
A	1	O	TRUE
B	2	O	TRUE
C	3	B	TRUE

B->C:1:3，原有节点总耗费为4,大于3。所以采用C->B，即C->B的数据更新到表中。

此时除去终点的节点都处理完，代表终点处理完成，即节点C处理完成。

5、处理流程总结

1、初始化表

2、选取起点节点

3、开始首次处理，即是用节点数据更新表数据

4、设置节点处理完成

5、选取耗费最少且未遍历完成的节点

6、重复4、5步操作。当节点为终点节点时推出循环

7、生成结果

三 php实现

//狄克斯特拉(Dijkstra) 算法 实现
class Test
{/*** $tableitem =['node'=>'','cost'=>'','prev'=>'']*/private $table = []; //计算开销数据private $result = []; //结算表private $data = [];private $start;private $end;public function __construct($data, $start, $end){$this->data = $data;$this->start = $start;$this->end = $end;}private function insert_tables($data){foreach ($data as $key => $value) {$this->insert_table($key);if (is_array($value)) {$this->insert_tables($value);}}}/*** 向table加数据** @param  [type] $node* @return void* @author wj* @date 2023-10-18*/private function insert_table($node){if (!isset($this->table[$node])) {$this->table[$node] = ['node' => $node,'cost' => false,'prev' => false,'isChecked' => false,];}}/*** 改table数据** @param  [type] $node* @param  [type] $cost* @param  [type] $prev* @return void* @author wj* @date 2023-10-18*/private function update_table($node, $cost, $prev){$info = $this->table[$node];if ($cost < $info['cost'] || false == $info['cost']) {$this->table[$node]['cost'] = $cost;$this->table[$node]['prev'] = $prev;}}/*** 处理节点** @param  boolean $node* @return void* @author wj* @date 2023-10-18*/private function deal_node($node = false){if (empty($node)) {$node = $this->get_need_deal_node();}if (empty($node) || !isset($this->data[$node])) {return false;}$usedata = $this->data[$node];$prev = $node;$table_cost = $this->table[$prev]['cost'];foreach ($usedata as $key => $cost) {$totalcost = $cost + (int) $table_cost;$this->update_table($key, $totalcost, $prev);}$this->table[$node]['isChecked'] = true;return true;}/*** 取得最小未处理节点** @param  [type] $node* @return void* @author wj* @date 2023-10-18*/private function get_need_deal_node(){$table = $this->table;$min_node = false;$cost = false;foreach ($table as $key => $value) {if ($value['isChecked'] || false === $value['cost']) {continue;}if ($value['cost'] < $cost || false === $cost) {$cost = $value['cost']; //最小开销$min_node = $key;}}return $min_node;}/*** 设定data 无没用分支 没有负权** @param  [type] $data* @param  [type] $start* @param  [type] $end* @return void* @author wj* @date 2023-10-18*/public function dotest(){//初始化table;$this->insert_tables($this->data);$node = $this->start;//处理节点while ($node) {$result = $this->deal_node($node);$node = $this->get_need_deal_node();if ($node == $this->end) {$this->table[$this->end]['isChecked'] = true;break;}}}public function getresult(){$end = $this->end;$result = [];$node = $end;while ($node) {$nodeinfo = $this->table[$node];$result[$nodeinfo['node']] = $nodeinfo;$node = $nodeinfo['prev'];}$result = array_reverse($result);$path = implode("->", array_keys($result));$lastnode = end($result);$cost = $lastnode['cost'];$data = ['result' => $result,'path' => $path,'cost' => $cost,];return $data;}
}
$data = ["O" => ["A" => 0,"B" => 1,],"A" => ["C" => 1,"B" => 2,],"B" => ["D" => 2,],"C" => ["D" => 3,],
];
$t = new Test($data, "O", "D");
$t->dotest();
$data = $t->getresult();
var_dump($data);

#执行结果
array(3) {'result' =>array(3) {'O' =>array(4) {'node' =>string(1) "O"'cost' =>bool(false)'prev' =>bool(false)'isChecked' =>bool(true)}'B' =>array(4) {'node' =>string(1) "B"'cost' =>int(1)'prev' =>string(1) "O"'isChecked' =>bool(true)}'D' =>array(4) {'node' =>string(1) "D"'cost' =>int(3)'prev' =>string(1) "B"'isChecked' =>bool(true)}}'path' =>string(7) "O->B->D"'cost' =>int(3)
}

这篇关于狄克斯特拉(Dijkstra) 算法 php实现的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---