44.讲最短路径：地图软件是如何计算出最优出行路径的_c# 根据地图算最短路径

问题：地图软件的最优路线是如何计算出来的吗？底层依赖了什么算法呢？

1. 算法解析

1.1 建模

把每个岔路口看作一个顶点，岔路口与岔路口之间的路看作一条边，路的长度就是边的权重。如果路是单行道，就在两个顶点之间画一条有向边；如果路是双行道，就在两个顶点之间画两条方向不同的边。这样，整个地图就被抽象成一个有向有权图。

代码表达：

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 implements Comparable<Vertex> {
    public int id; // 顶点编号ID
    public int dist; // 从起始顶点到这个顶点的距离
    public Vertex(int id, int dist) {
      this.id = id;
      this.dist = dist;
    }
    @Override
    public int compareTo(Vertex o) { // 按照dist从小到大排序
      if (o.dist > this.dist) return -1;
      else return 1;
    }
  }
}
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

1.2 最短路径算法Dijkstra

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 < v; ++i) { // 初始化dist为无穷大
    vertexes[i] = new Vertex(i, Integer.MAX_VALUE);
  }
  
  PriorityQueue<Vertex> heap = new PriorityQueue<>(); // 小顶堆
  boolean[] inQueue = new boolean[this.v]; // 标记是否进入过队列
  heap.add(vertexes[s]); // 先把起始顶点放到队列中
  vertexes[s].dist = 0;
  inqueue[s] = true;
  
  while (!heap.isEmpty()) {
    Vertex minVertex= heap.poll(); // 取dist最小的顶点
    
    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
      //找到一条到nextVertex更短的路径
      if (minVertex.dist + e.w < nextVertex.dist) {
        nextVertex.dist = minVertex.dist + e.w; // 更新dist
        predecessor[nextVertex.id] = minVertex.id; //更新前驱顶点
        if (inqueue[nextVertex.id] == false) { // 如果没有在队列中
          heap.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);
}
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

1.3 时间复杂度

在刚刚的代码实现中，最复杂就是while循环嵌套for循环那部分代码了。while循环最多会执行V次（V表示顶点的个数），而内部的for循环的执行次数不确定，跟每个顶点的相邻边的个数有关，我们分别记作E0，E1，E2，……，E(V-1)。如果我们把这V个顶点的边都加起来，最大也不会超过图中所有边的个数E（E表示边的个数）。

for循环内部的代码涉及从优先级队列取数据、往优先级队列中添加数据、更新优先级队列中的数据，这样三个主要的操作。我们知道，优先级队列是用堆来实现的，堆中的这几个操作，时间复杂度都是O(logV)（堆中的元素个数不会超过顶点的个数V）。

所以，综合这两部分，再利用乘法原则，整个代码的时间复杂度就是O(E*logV)。

1.4 工程实践

做工程不像做理论，一定要给出个最优解。理论上算法再好，如果执行效率太低，也无法应用到实际的工程中。对于软件开发工程师来说，我们经常要根据问题的实际背景，对解决方案权衡取舍。类似出行路线这种工程上的问题，我们没有必要非得求出个绝对最优解。很多时候，为了兼顾执行效率，我们只需要计算出一个可行的次优解就可以了。

• 虽然地图很大，但最短路径或者说较好的出行路径，并不会很“发散“，在地图上画个小区块，恰好覆盖两个点，执行Dijkstra算法，提高效率。
• 如果两点距离很远，比如北京海淀区到上海黄埔区，把北京和上海看作一个点，先规划大的路线，再细化到每个阶段的小路线。

2. 总结引申