图：最短路径算法

一时失言乱红尘 2024-04-17 05:57 56阅读 0赞

因为笔试题总是出这个，于是想写下思路

首先这个算法能解决从起始点，到各个点的最短路径问题.  
但是不能解决权值为负数的情况。并且时间复杂度为O(n^2),并且能用堆进行优化。

Dijkstra的主要思想：每次遍历到一个离源点最近的一个顶点，然后以该顶点为中心进行扩展，最终得到源点到其他顶点的最短路径。

步骤：  
1.将所有顶点分为两部分：已知最短路径集合P，和未知最短路径集合Q。最开始，已知最短路径只有原点一个顶点，book数组来记录那些顶点在P中，book\[i\]=1证明在顶点P中，为0表示在Q中。

2.设置源点s到自己的最短路径为0即dis\[s\]=0;若存在有源点能直接到达顶点i，把dis\[i\] = e\[s\]\[i\].同时把其他不能到达的设为不可达。（利用Integer.MAX\_VALUE）.

3.在集合Q中选择一个离源点最近的顶点u（即dis\[u\]最小）加入集合P。并考察所有以点u为起点的边，对每一条边做松弛操作。例如存在一条从u到v的边，那么可以将边u->v添加到尾部来拓展一条从s到v的路径，这条路径的长度是dis\[u\]+e\[u\]\[v\].如果这个值比目前已知的值dis\[v\]都小。用新值来替换老值。

4.重复第三步，如果集合Q为空，算法结束。最终dis数组中的值就是原点到所有顶点的最短路径。

Scanner scanner = new Scanner(System.in);
            int inf = Integer.MAX_VALUE;
    
            //读入n,m. n为顶点个数,m为边数
            int n = scanner.nextInt();
            int m = scanner.nextInt();
            //创建二维数组,保存权值
            int[][] e = new int[n+1][n+1];
            //最短路径数组
            int[] dis = new int[n+1];
            //标志数组
            int[] book = new int[n+1];
            //min
            int min ;
            // u是啥
            int u = 0;
            // ?
            int v;
    
    
            //1.初始化, 要么0    要么inf
            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] = Integer.MAX_VALUE;
                    }
    
                }
            }
    
            //2.读入边上的权值
            for(int i = 1;i<=m;i++){
    
                int x1,y1,z;
                x1 = scanner.nextInt();
                y1 = scanner.nextInt();
                z = scanner.nextInt();
                e[x1][y1] = z;
            }
    
            //3.初始化dis数组,这是1号顶点到其余各个顶点的初始路程
            for(int i = 1;i<=n;i++){
                dis[i] = e[1][i];
            }
    
            //4.book数组初始化,1就是在P已知，0在Q未知最短的路径
            for(int i = 1;i<=n;i++){
                book[i] = 0;
            }
            //让原点在P中
            book[1] = 1;
    
    
            //5.Dijkstra算法核心  ?1....n-1？
            for(int i = 1;i<=n-1;i++){
    
                //找到离1最近的点,寻找dis最小的
                min = Integer.MAX_VALUE;
                for(int j = 1;j<=n;j++){
                    if(book[j]== 0 && dis[j]<min){
                        min = dis[j];
                        u = j; //为啥不直接在这置 boo[j] = 1;
                    }
                }
                //6. 这个u点加入p中，考虑以u点出度，和从1到u的出度的最小距离
                book[u] = 1;
                //这个for to do?   从u开始到其他边的松弛操作
                for(v = 1;v <= n; v++){
    
    
                        if(e[u][v]<inf&&dis[v]>dis[u]+e[u][v])
                            dis[v] = dis[u]+e[u][v];
    
    
                }
    
    
            }
                //7.输出结果
            for(int i = 1;i<=n;i++){
    
                System.out.println(dis[i]);
    
            }