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=>...可看出,到红点的路径有多条:
?
图中的黄线都代表着到红点可能的遍历情况
代码
php代码实现:
地图抽象类,可自行实现宫格地图,或其他地图.
<?... $endKey = "{$value[0]}_{$value[1]}";
//判断是否之前有该点记录,没有则说明该点是未知路线
//有则判断路线是否最短