《啊哈！算法》——最短路径

Floyd-Warfare

多源最短路径。
可以处理带有负权边且无回路的图。
无法处理带有负权回路的图，因为此图没有最短路径。

import java.util.Arrays;

public class AlgorithmPractice {
    private static final int INF=10000;// 表示无穷大，即不可达。
    public static void main(String[] args) {
        int[][]edge={{1,2,1},{1,3,12},{2,3,9},{2,4,3},{3,5,5},{4,3,4},{4,5,13},{4,6,15},{5,6,4}};
        int n=6;
        int[][]dis=floydWarfare(initEdge(edge,n),n);
        System.out.println(Arrays.deepToString(dis));
    }
    public static int[][] floydWarfare(int[][]e,int n){
        // 用每一个点尝试松弛其它任意两点的路径
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                for(int k=1;k<=n;++k){
                    if(e[j][k]>e[j][i]+e[i][k]){
                        e[j][k]=e[j][i]+e[i][k];
                    }
                }
            }
        }
        return e;
    }
    public static int[][]initEdge(int[][]edge,int n){
        int[][]e=new int[n+1][n+1];// 边初始化
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(i==j){
                    e[i][j]=0;
                }else{
                    e[i][j]=INF;
                }
            }
        }
        // 读入边
        for(int i=0;i<edge.length;++i){
            e[edge[i][0]][edge[i][1]]=edge[i][2];
        }
        return e;
    }
}

Dijkstra

单源最短路径。
无法处理带有负权边的图，因为可能错过路径减小的情况（贪心策略），比如：
优化：基于堆优化即将确定最短路径的点的选择。

import java.util.Arrays;

public class AlgorithmPractice {
    private static final int INF=10000;// 表示无穷大，即不可达。
    public static void main(String[] args) {
        int[][]edge={{1,2,1},{1,3,12},{2,3,9},{2,4,3},{3,5,5},{4,3,4},{4,5,13},{4,6,15},{5,6,4}};
        int n=6;
        int[]dis=dijkstra(initEdge(edge,n),n);
        System.out.println(Arrays.toString(dis));
    }
    public static int[] dijkstra(int[][]e,int n){
        int[]dis=new int[n+1];// 最短路径
        dis[1]=0;
        // 最短路径的估计值
        for(int i=2;i<=n;++i){
            dis[i]=e[1][i];
        }

        boolean[] done=new boolean[n+1];// 确定最短路径的点为true
        done[1]=true;
        // 每次确定一个点的最短距离，共n-1次
        for(int i=1;i<n;++i){
            int min=INF;
            int point=0;
            // 最近的点
            for(int j=2;j<=n;++j){
                if(!done[j]&&dis[j]<min){
                    min=dis[j];
                    point=j;
                }
            }
            done[point]=true;
            // 通过该点对其它点进行松弛
            for(int k=2;k<=n;++k){
                if(dis[k]>dis[point]+e[point][k]){
                    dis[k]=dis[point]+e[point][k];
                }
            }
        }
        return dis;
    }
    public static int[][]initEdge(int[][]edge,int n){
        int[][]e=new int[n+1][n+1];// 边初始化
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                if(i==j){
                    e[i][j]=0;
                }else{
                    e[i][j]=INF;
                }
            }
        }
        // 读入边
        for(int i=0;i<edge.length;++i){
            e[edge[i][0]][edge[i][1]]=edge[i][2];
        }
        return e;
    }
}

Bellman-Ford

可以处理带有负权边的图。
一句话概括：对所有边进行最多n-1次松弛操作。
可以检测图中是否存在负权回路：如果在进行了n-1次松弛之后，存在dis[e[j][1]]>dis[e[j][0]]+e[j][2]的情况，则说明存在负权回路。
优化：
- 当某一轮松弛操作后，dis数组没有变化，则说明所有最短路径已经确定，即可退出for循环。
- 每次仅对最短路径估计值发生变化的定点的所有出边进行松弛操作。【因为在前一遍松弛后最短路径的估计值发生变化的点，才可能引起它们邻接点的最短路径估计值发生变化】。
最坏时间复杂度:O(NM），N：点数，M：边数。

import java.util.Arrays;

public class AlgorithmPractice {
    private static final int INF=10000;// 表示无穷大，即不可达。
    public static void main(String[] args) {
        int[][]edge={{1,2,1},{1,3,12},{2,3,9},{2,4,3},{3,5,5},{4,3,4},{4,5,13},{4,6,15},{5,6,4}};
        int n=6;
        int[]dis=bellmanFord(edge,n);
        System.out.println(Arrays.toString(dis));
    }
    public static int[] bellmanFord(int[][]e,int n){
        int[]dis=new int[n+1];// 最短路径
        dis[1]=0;
        // 最短路径的估计值
        for(int i=2;i<=n;++i){
            dis[i]=INF;
        }

        // 最多松弛n-1次
        for(int i=1;i<n;++i){
            // 通过每条边松弛相关的入点
            for(int j=0;j<e.length;++j){
                if(dis[e[j][1]]>dis[e[j][0]]+e[j][2]){
                    dis[e[j][1]]=dis[e[j][0]]+e[j][2];
                }
            }
        }
        return dis;
    }
}

最短路径算法对比分析

图片说明