zdaiot

404NotFound

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

发表于 分类于
本文字数： 6.9k 阅读时长 ≈ 6 分钟

首先，该文章来自于极客时间网站，王争的专栏——《数据结构与算法之美》，我这里只是做简单的解释、记录并添加自己的见解，只是作为个人笔记，若侵权，马上删除。最后建议直接去该网站上购买该课程看原作者的讲解，一来是支持作者，二来是作者写的确实不错。

关于图，之前提过两种针对无权图的搜索算法——深度优先搜索和广度优先搜索算法。那针对有权图，该如何计算两点之间的最短路径（经过的边的权重和最小）呢？经常使用地图软件时，会自动帮我们规划处最优路线。这个过程就涉及到本节要介绍的最短路径算法（Shortest Path Algorithm）。

算法解析

解决实际问题时，最重要的一点就是建模，也就是将复杂的场景抽象成具体的数据结构。对于这个问题，可以把地图抽象成图。把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，我们就在两个顶点之间画一条有向边；如果路是双行道，我们就在两个顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。对应的代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
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 算法。具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
// 因为Java提供的优先级队列，没有暴露更新数据的接口，所以我们需要重新实现一个
private class PriorityQueue { // 根据vertex.dist构建小顶堆
  private Vertex[] nodes;
  private int count;
  public PriorityQueue(int v) {
    this.nodes = new Vertex[v+1];
    this.count = v; // 一共有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]; // vertexes为数组
  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 数组的作用是为了还原最短路径，它记录每个顶点的前驱顶点。最后，我们通过递归的方式，将这个路径打印出来。
  • inqueue 数组是为了避免将一个顶点多次添加到优先级队列中。我们更新了某个顶点的 dist 值之后，如果这个顶点已经在优先级队列中了，就不要再将它重复添加进去了

整个过程对应的示例过程如下。下图中，(i, j) 中 i 表示从顶点到该点的最短距离，而 j 表示为得到这个最短距离，需要经过的上一个顶点。这里我对这个过程进行简单说明：首先初始顶点为0，将其添加到优先级队列中。初始顶点0出列，优先级队列中包含 {(10, 0), (15, 0)}，从可达距离中找到最短路径对应的顶点为 (10, 0) 并出列。此时优先级队列包含 {(12, 1), (15, 0), (25, 1)}。按照优先级队列出列顺序，顶点 (12, 1) 出列，考察其可达距离并更新优先级队列为 {(13,3), (15, 0), (24,3)}。按照优先级队列出队顺序，顶点 (13, 3) 出列，考察其可达距离并更新优先级队列为 {(15, 0), (18,2) }。按照优先级队列出队顺序，顶点 (15, 0) 出列，考察其可达距离并更新优先级队列为 {(18,2) }。则最后 (18, 2) 出列，完成整个算法。

输出最终顺序时，从顶点 (18, 2) 得到上一个顶点编号为2，从 (13, 3) 得到顶点2的上一个顶点编号为3，依次递归。

img

那么 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 算法，这样就可以避免遍历整个大图，也就大大提高了执行效率。

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

不过，在规划路线时，除了最短路径问题之外，还有两个关键问题——最少时间和最少红绿灯。

  • 对于最少时间问题，只需要将前面边的权重，从路的长度变成经过这段路所需要的时间。这个时间需要根据拥堵情况时刻变化。
  • 对于最少红绿灯问题，实际上把前面边的权重都变成1即可。这时可以用 Dijkstra 算法，还可以使用广度优先搜索算法（因为此时退化为无权图了）。

不过，这里给出的所有方案都非常粗糙。实际地图软件经常用之后讲到的 A* 启发式搜索算法。

总结引申

本节解释了Dijkstra 算法的原理和代码实现。其正确性的证明过程会涉及比较复杂的数学推导。这算法实现思路很经典，可以用来指导、解决其他问题。

例如，有一个翻译系统，只能针对某个词翻译。如果要翻译一整个句子，需要将句子拆成一个一个的单词，再丢给翻译系统。针对每个单词，翻译系统会返回一组可选的翻译列表，并且针对每个翻译打一个分，表示这个翻译的可信程度。

img

从每个单词的可选翻译列表中选择其中一个翻译，组合起来就是整个句子的翻译。整个句子的翻译得分就是每个单词的翻译得分之和。若希望得到得分最高的前 k 个翻译结果，怎么实现呢？

img

最简单是借助回溯算法，穷举所有的排列组合情况，然后选出得分最高的 k 个翻译结果。但这样时间复杂度很高为 $O(m^n)$，m 表示平均每个单词的可选翻译个数，n 表示一个句子中包含多少个单词。

实际上，这个问题可以借助 Dijkstra 算法的核心思想，非常高效的解决。把每个单词的可选翻译是按照分数从大到小排列，则 a0b0c0 肯定是得分最高组合结果。把 a0b0c0 及得分作为一个对象，放入到优先级队列中。

每次从优先级队列中取出一个得分最高的组合，并基于这个组合进行扩展。扩展的策略是每个单词的翻译分别替换成下一个翻译。比如 a0b0c0 扩展后，会得到三个组合，a1b0c0、a0b1c0、a0b0c1。把扩展后的组合，加入到优先级队列中。重复这个过程，直到获取到 k 个翻译组合或者队列为空。

img

那这种实现思路的时间复杂度是多少呢？

假设句子包含 n 个单词，每个单词平均有 m 个可选的翻译，要求得分最高的前 k 个组合结果。每次一个组合出队列，就对应着一个组合结果，我们希望得到 k 个，那就对应着 k 次出队操作。每次有一个组合出队列，就有 n 个组合入队列。优先级队列中出队和入队操作的时间复杂度都是 $O(logX)$，X 表示队列中的组合个数。所以，总的时间复杂度就是 $O(knlogX)$。那 X 到底是多少呢？k 次出入队列，队列中的总数据不会超过 $kn$，也就是说，出队、入队操作的时间复杂度是 $O(log(kn))$。所以，总的时间复杂度就是 $O(knlog(k*n))$，比之前的指数级时间复杂度降低了很多。

课后思考

  1. 在计算最短时间的出行路线中，如何获得通过某条路的时间呢？

    答：通过某条路的时间与①路长度②路况(是否平坦等)③拥堵情况④红绿灯个数等因素相关。获取这些因素后就可以建立一个回归模型(比如线性回归)来估算时间。其中①②④因素比较固定，容易获得。③是动态的，但也可以通过a.与交通部门合作获得路段拥堵情况；b.联合其他导航软件获得在该路段的在线人数；c.通过现在时间段正好在该路段的其他用户的真实情况等方式估算。

  2. 今天讲的是出行路线问题假设是开车出行的，那如果是公交出行呢？如果混合地铁、公交、步行，又该如何规划路线呢？

    答：混合公交、地铁和步行时：地铁时刻表是固定的，容易估算。公交虽然没那么准时，大致时间是可以估计的，步行时间受路拥堵状况小，基本与道路长度成正比，也容易估算。总之，感觉公交、地铁、步行，时间估算会比开车更容易，也更准确些。

------ 本文结束------
坚持原创技术分享，您的支持将鼓励我继续创作！

欢迎关注我的其它发布渠道