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

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;
    }
}

最短路径算法对比分析

图片说明

全部评论

相关推荐

不愿透露姓名的神秘牛友
昨天 18:54
点赞 评论 收藏
分享
不愿透露姓名的神秘牛友
11-20 19:57
已编辑
某大厂 golang工程师 23.0k*16.0, 2k房补,年终大概率能拿到
点赞 评论 收藏
分享
11-18 15:57
门头沟学院 Java
最终归宿是测开:这个重邮的大佬在重邮很有名的,他就喜欢打92的脸,越有人质疑他,他越觉得爽😂
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务