最短路径-Dijkstra算法
【摘要】 Dijkstra算法,又称"迪杰斯特拉算法",是从一个顶点到其余各顶点的最短路径算法，解决的是有向图中最短路径问题。迪杰斯特拉算法主要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。算法解析1: 设置2个顶点集合S,T S 存储已经找到的最短路径点的距离 T 存储未处理过的顶点2: 先把起点A存储到T.准备处理3: 获取到T的起点A,首先起点A到起点A的距离是0,直接存储到S:A=>...
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分别为起点,终点
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）