最短路径：地图软件是如何计算出最优出行路径的？

今天，从地图软件的路径规划问题讲起，带你看看常用的最短路径算法（Shortest Path Algorithm）。

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

算法解析

我们刚提到的最优问题包含三个：最短路线、最少用时和最少红灯。我们先解决最简单的，最短路线。

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

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

具体的代码实现，我放在下面了。于是，我们要求解的问题就转化为，在一个有向有权图中，求两个顶点的最短路径。

想要解决这个问题，有一个非常经典的算法，最短路径算法，更加准确地说，是单源最短路径算法（一个顶点到一个顶点）。提到最短路径算法，最出名的莫过于Dijkstra算法了。所以，我们现在来看，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值之后，如果这个顶点已经在优先级队列中了，就不要再将它重复添加进去了。

针对每个单词，我们从可选列表中，选择一个翻译，组合起来就是整个句子的翻译。每个单词的翻译的得分之和，就是整个句子的翻译得分。随意搭配单词的翻译，会得到一个句子不同的翻译。针对整个句子，我们希望计算出得分最高的前 k 个翻译结果，你会怎么编程来实现呢br>

我们来看，这种实现思路的时间复杂度是多少/p>

假设句子包含 n 个单词，每个单词平均有 m 个可选择的翻译，我们求得分数最高的前 k 个组合结果。每次一个组合出队列，就对应着一个组合结果，我们希望得到 k 个，那就对应着 k 次出队操作。每次有一个组合出队列，就有 n 个组合入队列。优先队列中出队和入队操作的时间复杂度都是O(logX)，X到底是多少呢/p>

k 次出队列，队列中的总数据不会超过 kn，也就是说，出队、入队操作的时间复杂度是O(log(kn))。所以，总的时间复杂度就是O(knlog(k*n))，比之前的指数级时间复杂度降低很多。