原创

最短路径-Dijkstra算法

温馨提示:
本文最后更新于 2019年03月14日,已超过 1,841 天没有更新。若文章内的图片失效(无法正常加载),请留言反馈或直接联系我

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分别为起点,终点

下面的输出为路线图

正文到此结束
本文目录