极客时间——数据结构与算法（44）最短路径：地图软件是如
何计算出最优出⾏路径的？
基础篇的时候，我们学习了图的两种搜索算法，深度优先搜索和⼴度优先搜索。这两种算法主要是针对⽆权图的搜索算法。针对有权图，也就是图中的每条边都有⼀个权重，我们该如何计算两点之间的最短路径（经过的边的权重和最⼩）呢？今天，我就从地图软件的路线规划问题讲起，带你看看常⽤的最短路径算法（Shortest Path Algorithm）。
像 Google 地图、百度地图、⾼德地图这样的地图软件，我想你应该经常使⽤吧？如果想从家开车到公司，你只需要输⼊起始、结束地址，地图就会给你规划⼀条最优出⾏路线。这⾥的最优，有很多种定义，⽐如最短路线、最少⽤时路线、最少红绿灯路线等等。作为⼀名软件开发⼯程师，你是否思考过，地图软件的最优路线是如何计算出来的吗？底层依赖了什么算法呢？
算法解析
我们刚提到的最优问题包含三个：最短路线、最少⽤时和最少红绿灯。我们先解决最简单的，最短路线。
解决软件开发中的实际问题，最重要的⼀点就是建模，也就是将复杂的场景抽象成具体的数据结构。针
对这个问题，我们该如何抽象成数据结构呢？
我们之前也提到过，图这种数据结构的表达能⼒很强，显然，把地图抽象成图最合适不过了。我们把每个岔路⼝看作⼀个顶点，岔路⼝与岔路⼝之间的路看作⼀条边，路的长度就是边的权重。如果路是单⾏道，我们就在两个顶点之间画⼀条有向边；如果路是双⾏道，我们就在两个顶点之间画两条⽅向不同的边。这样，整个地图就被抽象成⼀个有向有权图。
具体的代码实现，我放在下⾯了。于是，我们要求解的问题就转化为，在⼀个有向有权图中，求两个顶点间的最短路径。
public class Graph { // 有向有权图的邻接表表⽰
private LinkedList<Edge> adj[]; // 邻接表
private int v; // 顶点个数
public Graph(int v) {
this.v = v;
this.adj = new LinkedList[v];
for (int i = 0; i < v; ++i) {
this.adj[i] = new LinkedList<>();
}
}
public void addEdge(int s, int t, int w) { // 添加⼀条边
this.adj[s].add(new Edge(s, t, w));
}
private class Edge {
public int sid; // 边的起始顶点编号
public int tid; // 边的终⽌顶点编号
public int w; // 权重
public Edge(int sid, int tid, int w) {
this.sid = sid;
this.tid = tid;
this.w = w;
}
}
// 下⾯这个类是为了 dijkstra 实现⽤的
private class Vertex {
public int id; // 顶点编号 ID
public int dist; // 从起始顶点到这个顶点的距离
public Vertex(int id, int dist) {
this.id = id;
this.dist = dist;
}
}
}
想要解决这个问题，有⼀个⾮常经典的算法，最短路径算法，更加准确地说，是单源最短路径算法（⼀个顶点到⼀个顶点）。提到最短路径算法，最出名的莫过于 Dijkstra 算法了。所以，我们现在来看，Dijkstra 算法是怎么⼯作的。
这个算法的原理稍微有点⼉复杂，单纯的⽂字描述，不是很好懂。所以，我还是结合代码来讲解
// 因为 Java 提供的优先级队列，没有暴露更新数据的接⼝，所以我们需要重新实现⼀个
private class PriorityQueue { // 根据 vertex.dist 构建⼩顶堆
private Vertex[] nodes;
private int count;
public PriorityQueue(int v) {
}
public Vertex poll() { // TODO: 留给读者实现... }
public void add(Vertex vertex) { // TODO: 留给读者实现...}
// 更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度 O(logn)。
public void update(Vertex vertex) { // TODO: 留给读者实现...}
public boolean isEmpty() { // TODO: 留给读者实现...}
}
public void dijkstra(int s, int t) { // 从顶点 s 到顶点 t 的最短路径
int[] predecessor = new int[this.v]; // ⽤来还原最短路径
Vertex[] vertexes = new Vertex[this.v];
for (int i = 0; i < this.v; ++i) {
vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
}
PriorityQueue queue = new PriorityQueue(this.v);// ⼩顶堆
boolean[] inqueue = new boolean[this.v]; // 标记是否进⼊过队列
vertexes[s].dist = 0;
queue.add(vertexes[s]);
inqueue[s] = true;
while (!queue.isEmpty()) {
Vertex minVertex= queue.poll(); // 取堆顶元素并删除
if (minVertex.id == t) break; // 最短路径产⽣了
for (int i = 0; i < adj[minVertex.id].size(); ++i) {
Edge e = adj[minVertex.id].get(i); // 取出⼀条 minVetex 相连的边
Vertex nextVertex = vertexes[e.tid]; // minVertex-->nextVertex
if (minVertex.dist + e.w < nextVertex.dist) { // 更新 next 的 dist
nextVertex.dist = minVertex.dist + e.w;
predecessor[nextVertex.id] = minVertex.id;
if (inqueue[nextVertex.id] == true) {
queue.update(nextVertex); // 更新队列中的 dist 值
} else {
queue.add(nextVertex);
inqueue[nextVertex.id] = true;
}
程序员培训机构去到极客时间}
}
}
// 输出最短路径
System.out.print(s);
print(s, t, predecessor);
}
private void print(int s, int t, int[] predecessor) {
if (s == t) return;
print(s, predecessor[t], predecessor);
System.out.print("->" + t);
}
我们⽤ vertexes 数组，记录从起始顶点到每个顶点的距离（dist）。起初，我们把所有顶点的 dist 都初始化为⽆穷⼤（也就是代码中的Integer.MAX_VALUE）。我们把起始顶点的 dist 值初始化为 0，然后将其放到优先级队列中。
我们从优先级队列中取出 dist 最⼩的顶点 minVertex，然后考察这个顶点可达的所有顶点（代码中的 nextVertex）。如果 minVertex 的dist 值加上 minVertex 与 nextVertex 之间边的权重 w ⼩于 nextVertex 当前的 dist 值，也就是说，存在另⼀条更短的路径，它经过minVertex 到达 nextVertex。那我们就把 nextVertex 的 dist 更新为 minVertex 的 dist 值加上 w。然后，我们把 nextVertex 加⼊到优先级队列中。重复这个过程，直到到终⽌顶点 t 或者队列为空。
以上就是 Dijkstra 算法的核⼼逻辑。除此之外，代码中还有两个额外的变量，predecessor 数组和 inqueue 数组。
predecessor 数组的作⽤是为了还原最短路径，它记录每个顶点的前驱顶点。最后，我们通过递归的⽅式，将这个路径打印出来。打印路径的 print 递归代码我就不详细讲了，这个跟我们在图的搜索中讲的打印路径⽅法⼀样。如果不理解的话，你可以回过头去看下那⼀节。
inqueue 数组是为了避免将⼀个顶点多次添加到优先级队列中。我们更新了某个顶点的 dist 值之后，如果这个顶点已经在优先级队列中了，就不要再将它重复添加进去了。
看完了代码和⽂字解释，你可能还是有点懵，那我就举个例⼦，再给你解释⼀下。
理解了 Dijkstra 的原理和代码实现，我们来看下，Dijkstra 算法的时间复杂度是多少？
在刚刚的代码实现中，最复杂就是 while 循环嵌套 for 循环那部分代码了。while 循环最多会执⾏ V 次（V 表⽰顶点的个数），⽽内部的for 循环的执⾏次数不确定，跟每个顶点的相邻边的个数有关，我们分别记作 E0，E1，E2，……，E(V-1)。如果我们把这 V 个顶点的边都加起来，最⼤也不会超过图中所有边的个数 E（E 表⽰边的个数）。
for 循环内部的代码涉及从优先级队列取数据、往优先级队列中添加数据、更新优先级队列中的数据，这样三个主要的操作。我们知道，优先级队列是⽤堆来实现的，堆中的这⼏个操作，时间复杂度都是 O(logV)（堆中的元素个数不会超过顶点的个数 V）。
所以，综合这两部分，再利⽤乘法原则，整个代码的时间复杂度就是 O(E*logV)。
弄懂了 Dijkstra 算法，我们再来回答之前的问题，如何计算最优出⾏路线？
从理论上讲，⽤ Dijkstra 算法可以计算出两点之间的最短路径。但是，你有没有想过，对于⼀个超级⼤地图来说，岔路⼝、道路都⾮常多，对应到图这种数据结构上来说，就有⾮常多的顶点和边。如果为了计算两点之间的最短路径，在⼀个超级⼤图上动⽤ Dijkstra 算法，遍历所有的顶点和边，显然会⾮常耗时。那我们有没有什么优化的⽅法呢？
做⼯程不像做理论，⼀定要给出个最优解。理论上算法再好，如果执⾏效率太低，也⽆法应⽤到实际的⼯程中。对于软件开发⼯程师来说，我们经常要根据问题的实际背景，对解决⽅案权衡取舍。类似出⾏路线这种⼯程上的问题，我们没有必要⾮得求出个绝对最优解。很多时候，为了兼顾执⾏效率，我们只需要计算出⼀个可⾏的次优解就可以了。
有了这个原则，你能想出刚刚那个问题的优化⽅案吗？
虽然地图很⼤，但是两点之间的最短路径或者说较好的出⾏路径，并不会很“发散”，只会出现在两点之间和两点附近的区块内。所以我们可以在整个⼤地图上，划出⼀个⼩的区块，这个⼩区块恰好可以覆盖住两个点，但⼜不会很⼤。我们只需要在这个⼩区块内部运⾏ Dijkstra 算法，这样就可以避免遍历整个⼤图，也就⼤⼤提⾼了执⾏效率。
不过你可能会说了，如果两点距离⽐较远，从北京海淀区某个地点，到上海黄浦区某个地点，那上⾯的这种处理⽅法，显然就不⼯作了，毕竟覆盖北京和上海的区块并不⼩。
我给你点提⽰，你可以现在打开地图 App，缩⼩放⼤⼀下地图，看下地图上的路线有什么变化，然后再思考，这个问题该怎么解决。
对于这样两点之间距离较远的路线规划，我们可以把北京海淀区或者北京看作⼀个顶点，把上海黄浦
区或者上海看作⼀个顶点，先规划⼤的出⾏路线。⽐如，如何从北京到上海，必须要经过某⼏个顶点，或者某⼏条⼲道，然后再细化每个阶段的⼩路线。
这样，最短路径问题就解决了。我们再来看另外两个问题，最少时间和最少红绿灯。
前⾯讲最短路径的时候，每条边的权重是路的长度。在计算最少时间的时候，算法还是不变，我们只需要把边的权重，从路的长度变成经过这段路所需要的时间。不过，这个时间会根据拥堵情况时刻变化。如何计算车通过⼀段路的时间呢？这是⼀个蛮有意思的问题，你可以⾃⼰思考下。
每经过⼀条边，就要经过⼀个红绿灯。关于最少红绿灯的出⾏⽅案，实际上，我们只需要把每条边的权值改为 1 即可，算法还是不变，可以继续使⽤前⾯讲的 Dijkstra 算法。不过，边的权值为 1，也就相当于⽆权图了，我们还可以使⽤之前讲过的⼴度优先搜索算法。因为我们前⾯讲过，⼴度优先搜索算法计算出来的两点之间的路径，就是两点的最短路径。
不过，这⾥给出的所有⽅案都⾮常粗糙，只是为了给你展⽰，如何结合实际的场景，灵活地应⽤算法，让算法为我们所⽤，真实的地图软件的路径规划，要⽐这个复杂很多。⽽且，⽐起 Dijkstra 算法，地图软件⽤的更多的是类似 A* 的启发式搜索算法，不过也是在 Dijkstra 算法上的优化罢了，我们后⾯会讲到，这⾥暂且不展开。
总结引申
今天，我们学习了⼀种⾮常重要的图算法，Dijkstra 最短路径算法。实际上，最短路径算法还有很多，⽐如 Bellford 算法、Floyd 算法等等。如果感兴趣，你可以⾃⼰去研究。
关于 Dijkstra 算法，我只讲了原理和代码实现。对于正确性，我没有去证明。之所以这么做，是因为证明过程会涉及⽐较复杂的数学推导。这个并不是我们的重点，你只要掌握这个算法的思路就可以了。
这些算法实现思路⾮常经典，掌握了这些思路，我们可以拿来指导、解决其他问题。⽐如 Dijkstra 这个算法的核⼼思想，就可以拿来解决下⾯这个看似完全不相关的问题。这个问题是我之前⼯作中遇到的真实的问题，为了在较短的篇幅⾥把问题介绍清楚，我对背景做了⼀些简化。
我们有⼀个翻译系统，只能针对单个词来做翻译。如果要翻译⼀整个句⼦，我们需要将句⼦拆成⼀个⼀个的单词，再丢给翻译系统。针对每个单词，翻译系统会返回⼀组可选的翻译列表，并且针对每个翻译打⼀个分，表⽰这个翻译的可信程度。
针对每个单词，我们从可选列表中，选择其中⼀个翻译，组合起来就是整个句⼦的翻译。每个单词的翻译的得分之和，就是整个句⼦的翻译得分。随意搭配单词的翻译，会得到⼀个句⼦的不同翻译。针对整个句⼦，我们希望计算出得分最⾼的前 k 个翻译结果，你会怎么编程来实现呢？
当然，最简单的办法还是借助回溯算法，穷举所有的排列组合情况，然后选出得分最⾼的前 k 个翻译结果。但是，这样做的时间复杂度会⽐较⾼，是 O(m^n)，其中，m 表⽰平均每个单词的可选翻译个数，n 表⽰⼀个句⼦中包含多少个单词。这个解决⽅案，你可以当作回溯算法的练习题，⾃⼰编程实现⼀下，我就不多说了。
实际上，这个问题可以借助 Dijkstra 算法的核⼼思想，⾮常⾼效地解决。每个单词的可选翻译是按照分数从⼤到⼩排列的，所以 a0b0c0
肯定是得分最⾼组合结果。我们把 a0b0c0
及得分作为⼀个对象，放⼊到优先级队列中。
我们每次从优先级队列中取出⼀个得分最⾼的组合，并基于这个组合进⾏扩展。扩展的策略是每个单词的翻译分别替换成下⼀个单词的翻译。⽐如 a0b0c0
扩展后，会得到三个组合，a1b0c0、a0b1c0、a0b0c1
。我们把扩展之后的组合，加到优先级队列中。重复这个过程，直到获取到 k 个翻译组合或者队列为空。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。