图论算法之最短路径（Dijkstra、Floyd、Bellman-ford和SPFA）

1、图论最短路径概述

图论算法为了求解一个顶点到另一个顶点的最短路径，即如果从图中某一顶点（称为源点）到达另一顶点（称为终点）的路径可能不止一条，如何找到一条路径，使得沿此路径各边上的权值总和（即从源点到终点的距离）达到最小，这条路径称为最短路径（shortestpath）。

最短路径有很多特殊的情况，包括有向图还是无向图，有没有负权边等。通常解决图论中最短路径问题的算法有Dijkstra、Floyd、Bellman-ford和SPFA四种算法，下面逐一介绍各个算法的思想、流程和Java代码实现。

2、Dijkstra算法

迪杰斯特拉算法主要特点是以起始点为中心向外层扩展，直到扩展到终点为止。迪杰斯特拉算法采用的是贪心策略，将Graph中的节点集分为最短路径计算完成的节点集S和未计算完成的节点集T，每次将从T中挑选V0->Vt最小的节点Vt加入S，并更新V0经由Vt到T中剩余节点的更短距离，直到T中的节点全部加入S中，它贪心就贪心在每次都选择一个距离源点最近的节点加入最短路径节点集合。迪杰斯特拉算法只支持非负权图，它计算的是单源最短路径，即单个源点到剩余节点的最短路径，时间复杂度为O(n²),如果求解整个图各个节点之间的最短路径，那么使用迪杰斯特拉算法的时间复杂度就是O(n³)。

如果有权重是负值，则无法保证已经计算好的最短路径的节点构成最短路径，负数会影响结果。

Dijkstra算法适用场景：

一般算法书中都说适合于有向无环图（DAG）。但是并不代表无向图就不行，只要将源点和目标点的权重相互之间赋值成一个值即可。如果是有环图的话，对于每个节点都是做了一层遍历，也不会出现死循环和重复计算的问题，因此迪杰斯特拉算法是可以用在无向图和有环图中的，适合于求单源最短路径。如果想适用于多源最短路径，就要将每个节点都进行遍历，那么时间复杂度就是O(n³)。

把顶点的集合V分成两组：

• S：{已经求出最短路径的顶点}
• T=V-S：{尚未确定最短路径的顶点}

保证两点：

①每一个顶点对应一个距离值

S中顶点：从V0到此顶点的最短路径长度

T中顶点：从V0到此顶点的只包括S中顶点作中间顶点的最短路径长度

②S中各个顶点的距离值<=T中各个顶点的距离值。

将T中顶点按照最短路径递增的次序加入到S中，即每次从T中找出距离值最小的顶点加入到S中，直到S=V为止。

算法步骤：

• 初始时，令S={V0}，T={其余顶点}，T中顶点Vi对应的距离值，有：
  • 若存在<V0,Vi>，为<V0,Vi>弧上的权值；
  • 若不存在<V0,Vi>，为无穷大.
• 从T中选取一个其距离值为最小的顶点W，加入S，则S={V0, W}；
• 对T中其余顶点的距离值进行修改：若加进W作中间顶点，从V0到Vi的距离值比不加W的路径要短，则修改此距离值；
• 重复上述步骤，直到S中包含所有顶点，即S=V为止。

代码实现：

public class DijstraAlgorithm {
    //不能设置为Integer.MAX_VALUE，否则两个Integer.MAX_VALUE相加会溢出导致出现负权
    public static int MaxValue = 100000;
    
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入顶点数和边数:");
        //顶点数
        int vertex = input.nextInt();
        //边数
        int edge = input.nextInt();
 
        int[][] matrix = new int[vertex][vertex];
        //初始化邻接矩阵
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                matrix[i][j] = MaxValue;
            }
        }
        for (int i = 0; i < edge; i++) {
            System.out.println("请输入第" + (i + 1) + "条边与其权值:");
            int source = input.nextInt();
            int target = input.nextInt();
            int weight = input.nextInt();
            matrix[source][target] = weight;
        }
 
        //单源最短路径，源点
        int source = input.nextInt();
        //调用dijstra算法计算最短路径
        dijstra(matrix, source);
    }
 
    public static void dijstra(int[][] matrix, int source) {
        //最短路径长度
        int[] shortest = new int[matrix.length];
        //判断该点的最短路径是否求出
        int[] visited = new int[matrix.length];
        //存储输出路径
        String[] path = new String[matrix.length];
 
        //初始化输出路径
        for (int i = 0; i < matrix.length; i++) {
            path[i] = new String(source + "->" + i);
        }
 
        //初始化源节点
        shortest[source] = 0;
        visited[source] = 1;
 
        for (int i = 1; i < matrix.length; i++) {
            int min = Integer.MAX_VALUE;
            int index = -1;
 
            for (int j = 0; j < matrix.length; j++) {
                //已经求出最短路径的节点不需要再加入计算并判断加入节点后是否存在更短路径
                if (visited[j] == 0 && matrix[source][j] < min) {
                    min = matrix[source][j];
                    index = j;
                }
            }
 
            //更新最短路径
            shortest[index] = min;
            visited[index] = 1;
 
            //更新从index跳到其它节点的较短路径
            for (int m = 0; m < matrix.length; m++) {
                if (visited[m] == 0 && matrix[source][index] + matrix[index][m] < matrix[source][m]) {
                    matrix[source][m] = matrix[source][index] + matrix[index][m];
                    path[m] = path[index] + "->" + m;
                }
            }
 
        }
 
        //打印最短路径
        for (int i = 0; i < matrix.length; i++) {
            if (i != source) {
                if (shortest[i] == MaxValue) {
                    System.out.println(source + "到" + i + "不可达");
                } else {
                    System.out.println(source + "到" + i + "的最短路径为：" + path[i] + "，最短距离是：" + shortest[i]);
                }
            }
        }
    }
}

3、Floyd算法

Floyd算法又称为插点法，是一种利用动态规划的思想寻找给定的加权图中多源点之间最短路径的算法，与Dijkstra算法类似。该算法是一种在具有正或负边缘权重（但没有负环）的加权图中找到最短路径的算法，即支持负权值但不支持负权环。弗洛伊德算法采用的是动态规划思想，其状态转移方程如下：

其中matrix[i,j]表示i到j的最短距离, k是穷举i到j之间可能经过的中间点，当中间点为k时，对整个矩阵即从i到j的路径长度进行更新，对所有可能经过的中间点进行遍历以得到全局最优的最短路径。算法的单个执行将找到所有顶点对之间的最短路径长度，与迪杰斯特阿拉算法的计算目标有一些差异，迪杰斯特拉计算的是单源最短路径，而弗洛伊德计算的是多源最短路径，其时间复杂度为O(n³)。虽然它不返回路径本身的细节，但是可以通过对算法的简单修改来重建路径，我们利用这个思想，通过递归的方式访问每条路径经过的中间节点，对最终的路径进行输出。

算法思想：逐个顶点试探法。

算法步骤：

• 初始时设置一个n阶方阵，令其对角线元素为0，若存在弧<Vi,Vj>，则对应元素为权值；否则为无穷大——图的邻接矩阵；
• 逐步试着在原直接路径中增加一个中间顶点，若加入中间点后路径变短，则修改之；否则，维持原值；
• 所有顶点试探完毕，算法结束。

算法的代码实现：

public class FloydAlgorithm {
    public static int MaxValue = 100000;
    public static int[][] path;
    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        System.out.println("请输入顶点数和边数:");
        //顶点数
        int vertex = input.nextInt();
        //边数
        int edge = input.nextInt();
 
        int[][] matrix = new int[vertex][vertex];
        //初始化邻接矩阵
        for (int i = 0; i < vertex; i++) {
            for (int j = 0; j < vertex; j++) {
                matrix[i][j] = MaxValue;
            }
        }
 
        //初始化路径数组
        path = new int[matrix.length][matrix.length];
 
        //初始化边权值
        for (int i = 0; i < edge; i++) {
            System.out.println("请输入第" + (i + 1) + "条边与其权值:");
            int source = input.nextInt();
            int target = input.nextInt();
            int weight = input.nextInt();
            matrix[source][target] = weight;
        }
 
        //调用算法计算最短路径
        floyd(matrix);
    }
 
    //非递归实现
    public static void floyd(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                path[i][j] = -1;
             }
        }
 
        for (int m = 0; m < matrix.length; m++) {
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix.length; j++) {
                    if (matrix[i][m] + matrix[m][j] < matrix[i][j]) {
                        matrix[i][j] = matrix[i][m] + matrix[m][j];
                        //记录经由哪个点到达
                        path[i][j] = m;
                    }
                }
            }
        }
 
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix.length; j++) {
                if (i != j) {
                    if (matrix[i][j] == MaxValue) {
                        System.out.println(i + "到" + j + "不可达");
                    } else {
                        System.out.print(i + "到" + j + "的最短路径长度是：" + matrix[i][j]);
                        System.out.print("最短路径为：" + i + "->");
                        findPath(i, j);
                        System.out.println(j);
                    }
                }
            }
        }
    }
 
    //递归寻找路径
    public static void findPath(int i, int j) {
        int m = path[i][j];
        if (m == -1) {
            return;
        }
 
        findPath(i, m);
        System.out.print(m + "->");
        findPath(m, j);
    }
}

• 上述的三层循环中，第一层循环设置中间点k，第二层循环设置起始点i，第三层循环设置结束点j。

• 因为路径更新是根据新值和旧值比较获得的，最终的结果都是在最后一次迭代过程中对全局进行更新而得到的，中间的每次迭代只是一次局部调整而非最终结果。而不像迪杰斯特拉采用的贪心策略，每一次迭代都确定出一条最短路径，负权的出现使得不能保证每次迭代都是最优解。

4、Bellman-ford算法

BellmanFord算法功能：给定一个加权连通图，选取一个顶点，称为起点，求取起点到其它所有顶点之间的最短距离，其显著特点是可以求取含负权图的单源最短路径，可以来判断该图中是否有负权回路或者存在最短路径的点。

Bellman-Ford算法同样也是这样，它的每次循环也可以确定一个点的最短路，只不过代价很大，因为 Bellman-Ford每次循环都是操作所有边。既然代价这么大，相比Dijkstra算法，Bellman-Ford算法还有啥用？因为后者可以检测负权回路啊。Bellman-Ford算法的时间复杂度为 O(nm)，其中n 为顶点数，m为边数。

BellmanFord算法思想：

• 初始化所有点。每一个点保存一个值，表示从原点到达这个点的距离，将原点的值设为0，其它的点的值设为无穷大（表示不可达）。
• 进行循环，循环下标为从1到n－1（n等于图中点的个数）。在循环内部，遍历所有的边，进行松弛计算。
• 遍历途中所有的边（edge（u，v）），判断是否存在这样情况：如果d（v） > d (u) + w(u,v)，则返回false，表示途中存在从源点可达的权为负的回路；若不存在，则返回true，该数组记录的就是每一个点到源点的最小值。

算法代码实现：

/**  
 * 采用保存边的方式来存储图的的信息。  
 * p保存的是前驱节点，d保存的是源点到每一个点的最短距离。我们最后又做了一次判断，如果还有可以松弛  
 * 的边，那么可以保证的是图中有负权的环存在，这样的话就没有最短路径只说了，可以无限小。  
 */    
public class BellmanFord {    
    private static final int m = 10000;    
    public static void main(String[] args) {    
            
        Adge a1 = new Adge(0, 1, -1);    
        Adge a2 = new Adge(0, 2, 4);    
        Adge a3 = new Adge(1, 2, 3);     
        Adge a4 = new Adge(3, 1, 1);    
        Adge a5 = new Adge(1, 3, 2);    
        Adge a6 = new Adge(3, 2, 5);    
        Adge a7 = new Adge(1, 4, 2);    
        Adge a8 = new Adge(4, 3, -3);    
        Adge[] as = new Adge[]{a1, a2, a3, a4, a5, a6, a7, a8};    
            
        int[] d = new int[5];    
        int[] p = new int[5];    
        d[0] = 0;    
        p[0] = 0;    
        for (int i = 1; i < d.length; i++) {    
            d[i] = m;    
            p[i] = -1;    
        }    
        bellman_Ford(as, d, p);    
            
        for (int i = 0; i < d.length; i++) {    
            System.out.println(d[i]);    
        }    
    }    
    private static void bellman_Ford(Adge[] as, int[] d, int[] p){    
        for(int i = 1; i < d.length; i++) {    
            for (int j = 0; j < as.length; j++) {    
                if (d[as[j].getV()] > d[as[j].getU()] + as[j].getW()) {    
                    d[as[j].getV()] = d[as[j].getU()] + as[j].getW();    
                    p[as[j].getV()] = as[j].getU();    
                }    
            }    
        }    
        for (int j = 0; j < as.length; j++) {    
            if (d[as[j].getV()] > d[as[j].getU()] + as[j].getW()) {    
                System.out.println("有负环");    
            }    
        }    
    }    
}    
class Adge {    
    private int u;    
    private int v;    
    private int w;    
        
    public Adge(int u, int v, int w) {    
        this.u = u;    
        this.v = v;    
        this.w = w;    
    }    
    public int getU() {    
        return u;    
    }    
    public void setU(int u) {    
        this.u = u;    
    }    
    public int getV() {    
        return v;    
    }    
    public void setV(int v) {    
        this.v = v;    
    }    
    public int getW() {    
        return w;    
    }    
    public void setW(int w) {    
        this.w = w;    
    }       
}    

5、SPFA算法

Bellman-Ford算法时间复杂度比较高，在于Bellman-Ford需要递推n次，每次递推需要扫描所有的边，在递推n次的过程中，很多判断是多余的，所以考虑用队列优化，减少不必要的判断，这种算法称为SPFA（Shortest Path Faster Algorithm）

SPFA算法的流程：

使用一个优先队列来进行维护，初始时将源点加入队列，每次从队列中取出一个顶点，并对它所有相邻的节点进行松弛，如果某个顶点松弛成功，则将其入队，重复这样的过程，直至队列为空为止。时间复杂度在O(Km)(通常K为2左右)一个顶点可以多次入队，但是如果有顶点入队次数大于n次，那就存在负环，此时应当返回存在负环信息。

SPFA算法寻找单源最短路径的时间复杂度为O(m*E)。（其中m为所有顶点进队的平均次数，可以证明m一般小于等于2*图顶点个数，E为给定图的边集合）

SPFA算法过程：

在SPFA算法中同样可以用dist[]数组表示最短路长度，path数组保存路径，还需要设置cnt数组记录入队次数，vis数组记录当前是否在队列中

• 取出队列头结点u，扫描从顶点u出发的每条边，设每条边的终点为v，边的权值为w(u, v)。如果dist[u] + w < dist[v]，则将dist[v]修改成dist[u] + w<u, v>。修改path[v] = u，如果顶点v不在队列中，还需要将v加入队列并且入队次数加1。如果上述条件不成立就不做任何处理；

• 重复上一步操作直至队列为空或者某个顶点入队次数大于n。

SPFA算法代码实现：

import java.util.ArrayList;
import java.util.Scanner;

public class Spfa {
    
    public long[] result;         //用于得到第s个顶点到其它顶点之间的最短距离
    
    //内部类，用于存放图的具体边数据
    class edge {
        public int a;  //边的起点
        public int b;  //边的终点
        public int value;   //边的权值
        
        edge(int a, int b, int value) {
            this.a = a;
            this.b = b;
            this.value = value;
        }
    }
    /*
     * 参数n:给定图的顶点个数
     * 参数s:求取第s个顶点到其它所有顶点之间的最短距离
     * 参数edge:给定图的具体边
     * 函数功能：如果给定图不含负权回路，则可以得到最终结果，如果含有负权回路，则不能得到最终结果
     */
    public boolean getShortestPaths(int n, int s, edge[] A) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        result = new long[n];
        boolean[] used = new boolean[n];
        int[] num = new int[n];
        for(int i = 0;i < n;i++) {
            result[i] = Integer.MAX_VALUE;
            used[i] = false;
        }
        result[s] = 0;     //第s个顶点到自身距离为0
        used[s] = true;    //表示第s个顶点进入数组队
        num[s] = 1;       //表示第s个顶点已被遍历一次
        list.add(s);      //第s个顶点入队
        while(list.size() != 0) {
            int a = list.get(0);   //获取数组队中第一个元素
            list.remove(0);         //删除数组队中第一个元素
            for(int i = 0;i < A.length;i++) {
                //当list数组队的第一个元素等于边A[i]的起点时
                if(a == A[i].a && result[A[i].b] > result[A[i].a] + A[i].value) { 
                    result[A[i].b] = result[A[i].a] + A[i].value;
                    if(!used[A[i].b]) {
                        list.add(A[i].b);
                        num[A[i].b]++;
                        if(num[A[i].b] > n)
                            return false;
                        used[A[i].b] = true;   //表示边A[i]的终点b已进入数组队
                    }
                }
            }
            used[a] = false;        //顶点a出数组对
        }
        return true;
    }
    
    public static void main(String[] args) {
        Spfa test = new Spfa();
        Scanner in = new Scanner(System.in);
        System.out.println("请输入一个图的顶点总数n起点下标s和边总数p：");
        int n = in.nextInt();
        int s = in.nextInt();
        int p = in.nextInt();        
        edge[] A = new edge[p];
        System.out.println("请输入具体边的数据：");
        for(int i = 0;i < p;i++) {
             int a = in.nextInt();
             int b = in.nextInt();
             int value = in.nextInt();
             A[i] = test.new edge(a, b, value);
        }
        if(test.getShortestPaths(n, s, A)) {
             for(int i = 0;i < test.result.length;i++)
                 System.out.print(test.result[i]+" ");
        } else
             System.out.println("给定图存在负环，没有最短距离");
    }
}

6、四种算法的比较