单源最短路径

前言

给定一个带权有向图G=（V,E），其中每条边的权是一个实数。另外，还给定V中的一个顶点，称为源。现在要计算从源到其他所有各顶点的最短路径长度。这里的长度就是指路上各边权之和。这个问题通常称为单源最短路径问题。

求取单源最短路径一般有两种算法，Bellman ford算法以及Dijkstra算法。Bellman ford算法可适应有负权重的图，而Dijkstra算法则只能用于正权重无环图。

环路

如上图，一条最短路径是不可能包含环路的。环路包含两种情况，一种是负环路，如上图最下边的路径，它的最短路径为无限小，因为s、e、f、g的环路中，可以无限循环e、f，那么权重值可以无限降低。

最短路径也不可能包含正环路的，比如s、c、d、g的路径，不可能重复c、d，因为这样会增加路径的距离，完全可以减去正环路。

所以，最小路径中是不包含环路的。

松驰操作

求取单源最短路径需要用到松驰技术。对于每个节点来说，我们维持一个属性 v.d ，用来记录从源节点s到结点v的最短路径权重的上界。在算法开始时，使用如下方式进行初始化。

public void init_single_source(MatrixGraph graph, Vertex s){
    List<Vertex> list = graph.mList;
    for (Vertex vertex : list) {
        vertex.d = Integer.MAX_VALUE;
        vertex.pre = null;
    }
    s.d = 0;
}

设置源节点s.d等于0，其它节点v.d为无穷大，任意节点的前驱节点为空。

public void relax(Vertex u, Vertex v, int w){
    if (v.d > u.d + w) {
        v.d = u.d + w;
        v.pre = u;
    }
}

松驰操作，就是比较当前节点和前驱节点。如果前驱节点 d 加上边的权重值少于本节点的 d 值，则更新本节点 d 值。

Bellman ford算法

首先指出，图的任意一条最短路径既不能包含负权回路，也不会包含正权回路，因此它最多包含|v|-1条边。

其次，从源点s可达的所有顶点如果 存在最短路径，则这些最短路径构成一个以s为根的最短路径树。Bellman-Ford算法的迭代松弛操作，实际上就是按每个点实际的最短路径（虽然我们还不知道，但它一定存在）的层次，逐层生成这棵最短路径树的过程。

注意，每一次遍历，都可以从前一次遍历的基础上，找到此次遍历的部分点的单源最短路径。如：这是第i次遍历，那么，通过数学归纳法，若前面单源最短路径层次为1~（i-1）的点全部已经得到，而单源最短路径层次为i的点，必定可由单源最短路径层次为i-1的点集得到，从而在下一次遍历中充当前一次的点集，如此往复迭代，[v]-1次后，若无负权回路，则我们已经达到了所需的目的--得到每个点的单源最短路径。（注意：这棵树的每一次更新，可以将其中的某一个子树接到另一个点下）

最后，我们在第[v]次更新中若没有新的松弛，则输出结果，若依然存在松弛，则输出 false 表示无解。

public boolean bellman_ford(){
    MatrixGraph graph = initDigraph();
    Vertex s = graph.mList.get(0);
    init_single_source(graph, s);
    List<Vertex> list = graph.mList;
    MatrixEdge[][] edges = graph.mEdges;
    List<MatrixEdge> edgeList = new ArrayList<>();
    int arrayLength = graph.maxLength;
    MatrixEdge edge = null;
    for (int i = 0; i < arrayLength; i++) {
        for (int j = 0; j < arrayLength; j++) {
            edge = edges[i][j];
            if (edge != null) {
                edgeList.add(edge);
            }
        }
    }
    //每条边都要循环 list .size()-1 次，才能计算出正确答案。
    //因为s到最远的端点最多要经过 list .size()-1 条边，如果松驰次数少了
    //某个前顶点的d值之前改变后，就不会得到反馈。
    for (int i = 1; i < list.size(); i++) {
        for (int j = 0; j < edgeList.size(); j++) {
            edge = edgeList.get(j);
            relax(edge.v1, edge.v2, edge.weight);
        }
    }
    //第i个点经过i-1次数松驰就能得到最短距离
    //最远的点经过 edgeList.size()-1 次松驰也会得到最短距离。
    //所以，再次遍历，如果还存在能松驰的情况，那一定是有环路，这样的情况不存在最短距离。
    for (int i = 0; i < edgeList.size(); i++) {
        edge = edgeList.get(i);
        if (edge.v2.d > edge.v1.d + edge.weight) {
            return false;
        }
    }
    for (Vertex vertex : list) {
        System.out.println(vertex);
    }
    return true;
}

为什么一定要松驰 V-1 次，因为一个顶点到另一个顶点最多需要经过 V-1 条边。而且，我们在做松驰操作的时候，选取的第一条边未必就经过初始顶点，每次松驰所有边之后，顶点的d值均有可能减少，所以要松驰这么多次，以便得到最后正确答案。另外本算法的复杂度是 VE

Dijkstra算法

Dijkstra算法在运行过程中维持的关键信息是一组结点集合q，且q是最小优先队列，图中的所有结点均被保存在q中，不停地从q中取出第一个节点，也是d值最小的节点，将与d节点有边相连的节点进行松驰操作。

因为Dijkstra算法总是选择图中d值最小的点进行松驰，使用的是贪心策略。因为最短路径也一定是各条子路径都是最短的，所以此算法是有效的。

代码如下：

public void dijkstra(){
    MatrixGraph graph = initDigraph();
    Vertex s = graph.mList.get(0);
    init_single_source(graph, s);
    Vertex[] datas = new Vertex[graph.mList.size()];
    for (int i = 0; i < graph.mList.size(); i++) {
        datas[i] = graph.mList.get(i);
    }
    MinPriorityQueue queue = new MinPriorityQueue(datas);
    Vertex u = null;
    MatrixEdge edge = null;
    while (queue.size() > 0) {
        u = (Vertex) queue.heapExtractMin();
        int index = graph.mList.indexOf(u);
        for (int i = 0; i < VERTEX_NUM; i++) {
            edge = graph.mEdges[index][i];
            if (edge != null) {
                relax(edge.v1, edge.v2, edge.weight);
                //上一步进行了松驰操作，所以此处需要重新检测最小优先队列的属性
                //以维持queue仍是最小优先队列
                //此算法的关键就是正确设计最小优先队列
                queue.checkMinHeap();
            }
        }
    }
  for (Vertex vertex : graph.mList) {
      System.out.println(vertex);
  }
}

最小优先队列使用最小堆技术，代码详见本人github

如果不用最小堆，还有另一种实现：

/**
 * dijkstra算法的另一种实现
 * 核心原理都是顶点分成两部分，一部分是已经查验过的，一部分是未查验过的
 * 已检查的顶点集合已得到的最小距离，它们必然是其它顶点最短距离的一个环节
 * 每次在未查验顶点集合中，选取d值最小顶点，松驰d相关的所有边
 */
public void dijkstra2(){
    MatrixGraph graph = initDigraph();
    Vertex s = graph.mList.get(0);
    init_single_source(graph, s);
    List<Vertex> notCheckList = new ArrayList<>();
    notCheckList.addAll(graph.mList);
    List<Vertex> checkList = new ArrayList<>();
    Vertex u = null;
    MatrixEdge edge = null;
    while (notCheckList.size() > 0) {
        //找出最小的d值所在顶点
        int small = 0;
        for (int i = 0; i < notCheckList.size(); i++) {
            if (notCheckList.get(i).d < notCheckList.get(small).d) {
                small = i;
            }
        }
        u = notCheckList.get(small);
        int index = graph.mList.indexOf(u);
        for (int i = 0; i < VERTEX_NUM; i++) {
            edge = graph.mEdges[index][i];
            if (edge != null) {
                relax(edge.v1, edge.v2, edge.weight);
            }
        }
        notCheckList.remove(u);
        checkList.add(u);
    }
    for (Vertex vertex : graph.mList) {
        System.out.println(vertex);
    }
}

这两种写法其实背后的原理一样。