【笔记】数据结构与算法之最短路算法（SPFA）

QingYi.

这是bellmanFord算法的优化版本，还是比较好用的

[Java] 纯文本查看 复制代码

   

public class Main {
    private static int N= 1000010;    static int n,m;
    static int idx = 1;
    static int [] h = new int[N],ne = new int[N],e = new int[N], w = new int[N];
    // distance 距离
    static int [] dist = new int[N];
    static int INF= 0x3f3f3f3f;
    //statue  判断当前的点是不是最终确定的最短点
    static  boolean [] st = new boolean[N];
    static  int [] arr = new int[N];
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] s = bf.readLine().split(" ");
//        n个点m条边
        n = Integer.parseInt(s[0]);
        m = Integer.parseInt(s[1]);
        Arrays.fill(h,-1);
        for (int i = 0; i < m; i++) {
            String []  re = bf.readLine().split(" ");
            //分别是第一条边和第二条边
            int a = Integer.parseInt(re[0]);
            int b = Integer.parseInt(re[1]);
            //距离
            int c = Integer.parseInt(re[2]);
            add(a,b,c);
        }
        int res = spfa();
        if (res==-1) {
            System.out.println("impossible");
        }else {
            System.out.println(res);
        }
    }


    static void add(int a, int b, int c){
        //当前的idx的element是b
        e[idx] = b;
        //当前的idx的权重是c
        w[idx] = c;
        //当前的idx的next是head[a]
        ne[idx] = h[a];
        h[a] = idx++;
    }

    private static int spfa() {
        Arrays.fill(dist,INF);
        dist[1] = 0;
        Queue<Integer> queue = new LinkedList<>();
        queue.add(1);
        st[1] = true;
//        int head = 0,tail = -1;
//        arr[++tail] = 1;
//        while (head<=tail){
//            int temp = arr[head++];
//            st[temp] = false;
//            for (int i = h[temp];i!=-1;i= ne[i]){
//                int j = e[i];
//                if (dist[j]>dist[temp]+w[i]){
//                    dist[j] = dist[temp]+w[i];
//                    if (!st[j]){
//                        st[j] = true;
//                        arr[++tail] = j;
//                    }
//                }
//            }
//        }

        while (!queue.isEmpty()){
            //弹出一个值 把这个值设置为不可用
            int temp = queue.poll();
            st[temp] = false;
            //i从弹出的值开始遍历
            for (int i = h[temp];i!=-1;i= ne[i]){
                int j = e[i];
                if (dist[j]>dist[temp]+w[i]){
                    dist[j] = dist[temp]+w[i];
                    //如果j没用过，加入队列（加速）
                    if (!st[j]){
                        st[j] = true;
                        queue.add(j);
                    }
                }
            }

        }
        if (dist[n]!=INF){
            return dist[n];
        }
        return -1;
    }

}

在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中
在新标签打开所有链接复制所有链接URL复制所有链接URL（反向）复制所有链接标题 + URL复制所有链接标题 + URL (MD)复制所有链接标题 + URL (BBS)复制所有链接标题 + URL (筛选)复制所有链接标题 + URL (设置复制格式)在新标签页打开所有图片链接在一个标签页显示所有图片链接
复选框 - 选中
复选框 - 取消
复选框 - 反选
单选框 - 选中
单选框 - 取消
特殊单选框 - 选中

霏映

学习一下

cqlk001

谢谢分享 研究一下代码

amose

站里Java的内容也太少了把

QingYi.

amose 发表于 2021-1-3 21:44
站里Java的内容也太少了把

主要还是Python和易语言