一、最短路径分析：

像 Google 地图。百度地图、高德地图这样的地图软件，应该会经常使用吧？如果从家开到公司，你只需要输入起始地址、结束地址，地图就会给你规划一条最优路线。这里的最优，有很多种定义，比如最短路线、最少用时路线、最少红灯路线等等。作为一名软件开发工程师，你是否想过，地图软件的最优路线是如何计算出来的吗？底层依赖了什么算法？

二、数据结构

解决软件开发中的实际问题，最重要的一点是建模，也就是将复杂的场景抽象成具体的数据结构。针对这个问题，我们该如何抽象成数据结构呢？

我们之前也提到过，图这种结构的表达能力很强，显然，把地图抽象成图最合适不过了。我们把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。

三、算法

最出名的莫过于Dijkstra(迪杰斯特拉)算法了,
我们用vertexes 数组，记录从起始顶点到每个距离（dist）。起初，我们把所有顶点的dist都初始化为无穷大。我们把起始顶点的dist值初始化为0，类似于贪心思想+优先队列(堆)来解决。

我们从优先队列中取出dist最小的顶点minVertex，然后考察这个顶点可达的所有顶点（nextVertex）。如果minVertex的dist值加上minVertex与nextVerte之间边的权重w小于nextVertex 当前的dist值，也就是说，存在另一条理短的路径，它经过minVertex到达nextVertex。那我们就把nextVertex的dist更新为ninVertex的dist值加上w。然后，我们把nextVertex加入到优先级队列中。重复这个过程，直到找到顶点 t 或者队列为空。

以上就是dijkstras 算法 核心逻辑。除此之外，代码中还有两个额外的变量，predecessor数组和 inqueue数组。predecessor 数组的作用是为了还原最短路径，它记录每个顶点的前驱节点。最后通过递归的方式，将这个路径打印出来。

inqueue数组是为了避免将一个顶点多次添加到优先级队列中。我们更新了某个顶点dist值之后，如果这个顶点已经在优先级队列中了，就不要再将它重复添加进去了。[

](https://blog.csdn.net/every__day/article/details/88633171)
虽然地图很大，但是两点之间的最短路径或者说较好的出行路径，并不会很“发散”，只会出现在两点之间和两点附近的区块内。所以我们可以在整个大地图上，划出一个小区块，这个小区块恰好可以覆盖住两个点，但又不会很大。我们只需要在这个小区块内部运行Dijkstra算法，这样就可以避免遍历整个大图，也就大大提高了执行效率。

不过你你可能会说了，如果两点距离比较远，从北京海淀区某个地点，到上海黄浦区某个地点，那上面的这种处理方法，显然就不工作了，毕竟覆盖北京和上海的区块并不小。

对于这样两点之间的距离较远的路线规划，我们可以氢北京海淀区或者北京看作一个顶点，把上海黄浦区或者上海看作一个顶点，先规划大的出行路线。比如从北京到上海，必须要经过某几个顶点，或者某几条干道，然后再细化每个阶段的小路线。

这样，最短路径问题就解决了。我们再来看另外两个问题，最少时间和最少红灯。

前面讲最短路径的时候，每条边的权重是路的长度。在计算最少时间的时候，算法还是不变，我们只需要把边的权重，从路的长度变成经过这段路所需要的时间。不过，这个时间会根据拥堵情况时刻变化。如何计算车通过一段路的时间呢？这是一个蛮有意思的问题，你可以自己思考下。

每经过一条边，就要经过一个红绿灯。关于最少红绿灯的出行方案，实际上，我们只需要把每条边的权值改为1即可，算法还是不变，可以继续使用前面讲的Dijkstra算法。不过，边的权值为1，也就相当于无权图了，我们还可以使用之前讲过的广度优先搜索算法。因为我们前面讲过，广度优先搜索算法计算出来的两点之间的路径，就是两点的最短路径。

不过，这里给出的所有方案都非常粗糙，地图软件用的更多是类似 A* 启发式搜索算法，不过也是在 Dijkstra算法上的优化罢了。

四、如下场景，找1到6的最短距离

image.png

五、网格地图中的启发式算法

5.1 曼哈顿距离
标准的启发式函数是曼哈顿距离（Manhattan distance）

考虑代价函数并找到从一个位置移动到邻近位置的 最小代价D
曼哈顿距离——两点在南北方向上的距离加上在东西方向上的距离
即 D(I，J)= |XI - XJ| + |YI - YJ|
因此，启发式函数应该是曼哈顿距离的D倍：

  1. H(n) = D * (abs ( n.x – goal.x ) + abs ( n.y – goal.y ) )

image.png

5.2 对角线距离

如果在地图中允许对角运动，那么需要一个不同的启发函数
（4 east, 4 north）的曼哈顿距离将变成8 D，然而可以简单地移动（4 northeast）代替
所以启发函数应该是4 D
假设直线和对角线的代价都是D：

  1. h(n) = D * max(abs(n.x - goal.x), abs(n.y - goal.y))

image.png

5.3 欧几里得距离

然而，如果是这样的话，直接使用A 时将会遇到麻烦
因为代价函数g ( n ) g(n)g(n)不会匹配启发函数h ( n ) h(n)h(n)
因为欧几里得距离比曼哈顿距离和对角线距离都短
仍可以得到最短路径，不过A将运行得更久一些
image.png

5.4 平方后的欧几里得距离

image.png[

](https://blog.csdn.net/every__day/article/details/88633171)