【笔记】数据结构与算法之Dijkstra（堆优化版）

QingYi.

适用于稀疏的边
复杂度O（mlogn），比起昨天朴素版的Dijkstra的O（n^2）快不少

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Main {
    private static int N= 1000010;
    static int n,m;
    static PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{return a[1] - b[1];});//堆
    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];
    //statue  判断当前的点是不是最终确定的最短点
    static  boolean [] st = new boolean[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);
        }
        System.out.println(dijkstra());
    }


    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 dijkstra() {
        //初始化
        Arrays.fill(dist, 0x3f3f3f3f);
        // 第一个点到自己的距离是0
        dist[1] = 0;
        //1 to itself distance
        pq.add(new int[]{1,0});
        while (!pq.isEmpty()){
            int [] cur = pq.poll();
            int node = cur[0];
            int distance = cur[1];
            //如果存在的就直接continue
            if (st[node]){
                continue;
            }
            st[node] = true;
            //从h[node]开始
            for(int i = h[node];i!=-1;i = ne[i]){
                int j = e[i];
                int curDistance = distance+w[i];
                if (dist[j]>curDistance){
                    dist[j] = curDistance;
                    //大的dist[j]
                    pq.add(new int[]{j,dist[j]});
                }
            }
        }
        //4个3f  如果不等于0x3f3f3f3f说明找到了 return dist[n] 否则return -1；
        if(dist[n]!=0x3f3f3f3f)  return dist[n];
        return -1;
    }
}

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

Rainsup

楼主  请问下  有java算法的教程吗   你要同意我就开一个悬赏贴给你   
还有就是我想问一下， 学算法主要应用在那些领域  ，学了算法之后是不是有一个质的提升

QingYi.

Rainsup 发表于 2021-1-1 11:53
楼主  请问下  有java算法的教程吗   你要同意我就开一个悬赏贴给你   
还有就是我想问一下， 学算法主要 ...

1.算法教程：这个东西肯定是有的，因为我不确定哪些是优质的教程，暂且不做推荐；且算法无关语言，是一种思想，我学的算法很多都不是用java写的，例如有c、c++和Python，经过理解再转为java代码的。
2.算法的目的：我只是觉得这个东西很好玩，然后呢我本身也是学计算机的，学习计算机相关的内容也是我的兴趣所在，至于算法用在用在哪些领域，就比如图这个算法吧，地图软件就是使用图的知识，求最短路，或者步行距离最短，还有飞机中转次数最少（没有直达）

猛男十年

不错学习了