最短路径

算法解析

建模：将复杂的场景抽象成具体的数据结构。

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

地图中起点到终点的最短路径问题转化为在一个有向有权图中，求两个顶点间的最短路径。

有向有权图

public class Graph {
    private LinkedList<Edge> adj[];//邻接表
    private int v;//顶点个数

    publicGraph(int v) {
        this.v = v;
        this.adj = new LinkedList[v];//v个链表
        for(int i = 0; i < v; ++i) {
            this.adj[i] = new LinkedList<>();//每个编号的顶点都存了一个链表
        }
    }

    //添加一条边
    public void addEdge(int s, int t, int w) {
        this.add[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 = sid;
            this.w = w;
        }
    }

    //
    private class Vertex {
        public int id;//顶点编号ID
        public int dist;//从起始顶点到这个顶点的距离
        public Vertex(int id, int dist) {
            this.id = id;
            this.dist = dist;
        }
    }
}

最短路径算法-单源最短路径算法(一个顶点到一个顶点)。

将每个顶点到起始顶点的距离初始化为无穷，然后从起始点开始，将其加入一个优先级队列中，从优先级队列中取出到源点距离最小的顶点，然后比较其周围顶点离源点的距离是否大于其到源点的距离+其到周围顶点的距离，如果大于的话，更新周围顶点到源点的距离为较小的值以及其前序节点，并将其加入优先级队列中(如果已经加入过，就更新)，再取出优先级队列中的距离最小值，循环往复，直到取出终止顶点t，或者优先级队列为空。此时倒序输出终止顶点t的前序节点，前序节点的前序节点。。。直到前序节点为起始顶点s，此路径即为最短路径。

Dijkstra算法：
动态规划算法，求得的解是全局最优解。

Dijkstra算法类似BFS算法，每次找到跟起点最近的顶点，往外扩展。

Dijkstra算法

//带更新数据接口的优先级队列
private class PriorityQueue {
    //根据vertex.dist构建小顶堆
    private Vertex[] nodes;
    private int count;
    public PriorityQueue(int v) {
        this.nodes = new Vertex[v+1];//从下标1开始存数据
        this.count = v;
    }
    public Vertex poll() {}
    public void add(Vertex vertex) {}
    //更新结点的值，并且从下往上堆化，重新符合堆的定义。时间复杂度O(logn)
    public void update(Vertex vertex) {
        Vertex v = nodes[vertex.id];
        v.dist = vertex.dist;
        //todo 堆化
    }
    public boolean isEmpty() {}
}

//从顶点s到顶点t的最短路径
public void dijkstra(int s, int 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);//取出一条minVertex相连的边
            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.is] == true) {
                    queue.update(nextVertex);//更新队列中的dist值，自动更新位置(堆化)
                    //queue.remove(nextVertex);
                    //queue.add(nextVertex);
                } 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。把nextVertex的dist更新为minVertex的dist值加上w。然后把nextVertex加入到优先级队列中。重复这个过程，直到找到终止顶点t或者队列为空。

predecessor数组的作用是为了还原最短路径，它记录每个顶点的前驱顶点。最后通过递归的方式，将这个路径打印出来（深度广度优先搜索）。

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

时间复杂度

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

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

综合之后，利用乘法原则，整个代码的时间复杂度为O(E*logV)。

实际应用

实际问题没有必要非得求出个绝对最优解，很多时候为了兼顾执行效率，只需要计算出一个可行的次优解就可以。

1. 超级大地图最短路径
   超级大地图，两点之间的最短路径或者说较好的出行路径，并不会很“发散”，只会出现在两点之间和两点附近的区块内。可以在整个大地图上，划出一个小的区块，这个小的区块恰好可以覆盖住两个点，但是又不会很大，只需要在这个小区块内部运行Dijkstra算法，这样就可以避免遍历整个大图，也就大大提高了执行效率。

   对于两点之间距离较远的路线规划，先规划大的出行路线，然后再细化每个阶段的小路线。

2. 最少时间
   在计算最少时间的时候，算法与最短路径相同，只需要把边的权重，从路的长度变成经过这段路所需要的时间。

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

4. 翻译
   只针对单个词翻译的翻译系统。
   翻译一整个句子，将句子拆分成一个一个的单词，再丢给翻译系统。针对每个单词，翻译系统会返回一组可选的翻译列表，并且针对每个翻译打一个分，表示这个翻译的可信程度。
   针对每个单词，从可选列表中，选择其中一个翻译，组合起来就是整个句子的翻译。每个单词的翻译的得分之和，就是真个句子的翻译得分。随意搭配单词的翻译，会得到一个句子的不同翻译。针对整个句子，编程计算出得分最高的前k个翻译结果。

   • 回溯算法，穷举所有的排列组合情况，然后选出得分最高的前k个翻译结果。时间复杂度为O(mⁿ)，m表示平均每个单词的可选翻译个数，n表示一个句子中包含的单词数量。

   • Dijkstra算法，每个单词的可选翻译是按照分数从大到小排列的，a₀b₀c₀肯定是得分最高组合结果。把其及其得分作为一个对象，放入优先级队列中。

     每次从优先级队列中取出一个得分最高的组合，并给予这个组合进行扩展。扩展的策略是每个单词的翻译分别替换成下一个单词的翻译。a₀b₀c₀扩展后会得到三个组合，a₁b₀c₀、a₀b₁c₀、a₀b₀c₁。把扩展之后的组合，加到优先级队列中。重复这个过程，直到获取到k个翻译组合或者队列为空。

     时间复杂度，假设句子包含n个单词，每个单词平均有m个可选的翻译，求得分最高的前k个组合结果。每次一个组合出队列，就对应着一个组合结果，希望得到k个，就对应着k次出队操作。每次有一个组合出队列，就有n个组合入队列。优先级队列中出队和入队操作的时间复杂度都是O(logX)，X表示队列中的组合个数。总的时间复杂度就是O(k*n*logX)。
     k次出入队列，队列中的总数据不会超过k*n，也就是说，出队、入队操作的时间复杂度是O(log(k*n))。总的时间复杂度为O(k*n*log(k*n))。