Dijkstra算法,又称"迪杰斯特拉算法",是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。
算法解析
1: 设置2个顶点集合S,T
S 存储已经找到的最短路径点的距离
T 存储未处理过的顶点
2: 先把起点A存储到T.准备处理
3: 获取到T的起点A,首先起点A到起点A的距离是0,直接存储到S:A=>{length:0,route:A},
4: 然后通过起点,获取起点周围的几个点和距离,例如B距离1,C距离5,D距离3,存储到T
5: 起点到周围的点都是当前的最短路径,直接存储到S:B=>{length:1,route:AB},C=>{length:5,route:AC},以此类推
6: 继续获取周围B,C,D 周围的点和距离,例如B周围点为 E,C 距离为1,1,存储到T
7: 获取到T的E,C,E直接存储,由于C在5的时候已经存储,length为5,而A=>B length为1,B=>C length为 1,1+1< 5,则直接覆盖更新掉之前的C距离,改为:C=>{length:2,route:ABC} (假想情况,为了方便理解更新最短路径),如果长度大于之前的,则不处理该点
8: 继续获取到E,C周围的点.存储到T
9: 如果已经获取到了终点(可以不需要终点,则之前遍历全部点),则不再获取终点周围的点
重复7,8步骤,直到T不存在数据
在这个过程中,可以保证起点到所有点都是最短路径
算法图解过程
例如 10x10 宫格图中:
以绿色方格为起点,红色为终点,黑色为障碍物.
1: 首先绿色方格距离为0,直接存储,并获取到周围3个点(不考虑斜边和障碍物),存储到T
2: 遍历T的3个点,距离都为1,直接存储
3: 遍历3个点周围的点,存储到T
4: 取出T点的其他待处理点,判断路径长度,如果小于之前存储的,则覆盖更新路径
.
.
.
其他过程略
下图是遍历步骤,颜色渐变代表了遍历的次数不同
可看出,到红点的路径有多条:
图中的黄线都代表着到红点可能的遍历情况
代码
php代码实现:
地图抽象类,可自行实现宫格地图,或其他地图.
<?php /** * Created by PhpStorm. * User: Tioncico * Date: 2019/3/15 0015 * Time: 9:07 */ namespace Dijkstra; abstract class MapHandleAbstract { protected $map = \[\];//地图 protected $start;//起点 protected $end;//终点 //abstract public function drawMap();//绘制地图 abstract public function getAdjacent($coordinates);//获取相邻点 abstract public function getLength($start,$end);//获取2点的距离 abstract public function getStart(); abstract public function setStart($start); abstract public function getEnd(); abstract public function setEnd($end); }
宫格地图实现类;
<?php /** * Created by PhpStorm. * User: Tioncico * Date: 2019/3/15 0015 * Time: 9:14 */ namespace Dijkstra; class GridMap extends MapHandleAbstract { protected $map = \[\]; protected $start; protected $end; protected $x; protected $y; public function __construct($x, $y) { $this->x = $x; $this->y = $y; $this->initMap(); } public function initMap() { $map = \[\]; for ($i = 0; $i < $this->x; $i++) { for ($j = 0; $j < $this->y; $j++) { $map\[$i\]\[$j\] = 0; } } $this->map = $map; } public function drawMap() { echo " 0 1 2 3 4 5 6 7 8 9 \\n"; for ($i = 0; $i < $this->y; $i++) { echo "$i "; for ($j = 0; $j < $this->x; $j++) { echo " \[{$this->map\[$j\]\[$i\]}\] "; } echo "\\n\\n"; } // TODO: Implement drawMap() method. } public function getLength($start, $end) { return abs($start\[0\]-$end\[0\])+abs($start\[1\]-$end\[1\]); // TODO: Implement getLength() method. } /** * 获取相邻点 * getAdjacent * @author Tioncico * Time: 15:15 */ public function getAdjacent($coordinate) { $data = \[\]; $map = $this->map; //4个相邻点 if (isset($map\[$coordinate\[0\] - 1\]\[$coordinate\[1\]\]) && $map\[$coordinate\[0\] - 1\]\[$coordinate\[1\]\] !== 'x') { $data\[\] = \[$coordinate\[0\] - 1, $coordinate\[1\]\]; } if (isset($map\[$coordinate\[0\] + 1\]\[$coordinate\[1\]\]) && $map\[$coordinate\[0\] + 1\]\[$coordinate\[1\]\] !== 'x') { $data\[\] = \[$coordinate\[0\] + 1, $coordinate\[1\]\]; } if (isset($map\[$coordinate\[0\]\]\[$coordinate\[1\] - 1\]) && $map\[$coordinate\[0\]\]\[$coordinate\[1\] - 1\] !== 'x') { $data\[\] = \[$coordinate\[0\], $coordinate\[1\] - 1\]; } if (isset($map\[$coordinate\[0\]\]\[$coordinate\[1\] + 1\]) && $map\[$coordinate\[0\]\]\[$coordinate\[1\] + 1\] !== 'x') { $data\[\] = \[$coordinate\[0\], $coordinate\[1\] + 1\]; } //斜边暂时不计 return $data; } /** * @return mixed */ public function getStart() { return $this->start; } /** * @param mixed $start */ public function setStart($start): void { $this->map\[$start\[0\]\]\[$start\[1\]\] = 'S'; $this->start = $start; } /** * @return mixed */ public function getEnd() { return $this->end; } /** * @param mixed $end */ public function setEnd($end): void { $this->map\[$end\[0\]\]\[$end\[1\]\] = 'E'; $this->end = $end; } public function setHinder($coordinates) { foreach ($coordinates as $value) { $this->map\[$value\[0\]\]\[$this->map\[1\]\] = 'x'; } } public function addHinder($coordinate) { $this->map\[$coordinate\[0\]\]\[$coordinate\[1\]\] = 'x'; } }
算法实现类
<?php /** * Created by PhpStorm. * User: Tioncico * Date: 2019/3/1 0001 * Time: 10:04 */ namespace Dijkstra; class Dijkstra { protected $mapHandle = null; protected $save = \[\]; protected $list = \[\]; public function __construct(MapHandleAbstract $mapHandleClass) { $this->mapHandle = $mapHandleClass; } /** * 执行 * exec * @param $start * @param $end * @return array * @author Tioncico * Time: 9:31 */ public function exec($start, $end) { $this->mapHandle->setStart($start); $this->mapHandle->setEnd($end); $this->addList($start, 0, \[\]); $this->dijkstra($end); return $this->save; } /** * 算法 * dijkstra * @param null $end * @return array * @author Tioncico * Time: 9:38 */ public function dijkstra($end = null) { $save = $this->save; while ($value = array_shift($this->list)) { $endKey = "{$value\[0\]}_{$value\[1\]}"; //判断是否之前有该点记录,没有则说明该点是未知路线 //有则判断路线是否最短 $totalLength = $value\['totalLength'\]; $length = $value\['length'\]; $route = $value\['route'\]; if (!isset($save\[$endKey\])) { $save\[$endKey\]\['totalLength'\] = $totalLength + $length; $route\[\] = \[$value\[0\],$value\[1\]\]; $save\[$endKey\]\['route'\] = $route; if ($value == $end) { return $save; } $this->addList($value, $totalLength + $length, $route); } else { if ($save\[$endKey\]\['totalLength'\] > $totalLength + $length) { $save\[$endKey\]\['totalLength'\] = $totalLength + $length; $route\[\] = \[$value\[0\],$value\[1\]\]; $save\[$endKey\]\['route'\] = $route; if ($value == $end) { return $save; } $this->addList($value, $totalLength + $length, $route); } } } $this->save = $save; return $save; } public function addList($coordinate, $totalLength, $route) { //获取起始点的周围点 $data = $this->mapHandle->getAdjacent($coordinate); $list = \[\]; foreach ($data as $key=>$va) { $list\[$key\]\['totalLength'\] = $totalLength; $list\[$key\]\['route'\] = $route; $list\[$key\]\['length'\] = $this->mapHandle->getLength($coordinate,$va); $list\[$key\]\[0\] = $va\[0\]; $list\[$key\]\[1\] = $va\[1\]; } $this->list = array_merge($this->list, $list); return $this->list; } }
调用方法:
<?php /** * Created by PhpStorm. * User: Tioncico * Date: 2019/3/1 0001 * Time: 10:04 */ include "./vendor/autoload.php";//自动加载 $map = new \\Dijkstra\\GridMap(10,10); $map->addHinder(\[5,5\]); $map->addHinder(\[5,4\]); $map->addHinder(\[5,3\]); $map->addHinder(\[4,3\]); $map->addHinder(\[3,3\]); $map->addHinder(\[5,6\]); $map->addHinder(\[5,7\]); $map->addHinder(\[4,7\]); $map->addHinder(\[3,7\]); $map->addHinder(\[2,7\]); //var_dump($map); $test = new \\Dijkstra\\Dijkstra($map); $save = $test->exec(\[4,5\],\[6,5\]); $map->drawMap(); //var_dump($save); foreach ($save\['6_5'\]\['route'\] as $value) { echo "{$value\[0\]}_{$value\[1\]}\\n"; }
最后附上一张输出图:
x代表障碍物,S,E分别为起点,终点
下面的输出为路线图
