堆优化版Dijkstra（Java）

题目解析

Dijkstra算法逻辑：以源点为中心，逐步遍历离源点最近的节点（权重和最小），并更新该节点出度对应节点的离源点最小值。
朴素版Dijkstra算法的时间复杂度是O(n^2)的，而确定节点与源点的距离顺序需要遍历所有未计算完成最小值的节点，这一步耗时是O(n)的。如果，能够快速的确定该最小值，就能有效降低Dijkstra算法的时间复杂度。采用小顶堆结构后，获取最小值的时间复杂度为O(1)，但是由于维护小顶堆结构的时间复杂度是logn，所以堆优化版的Dijkstra算法时间复杂度就是mlogn；由于是稀疏图，所以mlogn将远小于朴素Dijkstra算法的O(n^2);

基于此，掌握朴素版Dijkstra算法后，优化版的代码也就很容易实现：
1.维护一个由节点编号、该节点与源点距离的小顶堆（以与源点距离为比较依据）；
2.将朴素版遍历节点所有出度，找出最小权的代码替换为从小顶堆获取；
3.维护小顶堆中的对象；
当然，还有一个前提：将朴素版邻接矩阵变更为邻接表。

时间复杂度（$O(mlogn)$）

Java 代码

class Main{
    //邻接表
    private static Map<Integer,Integer> adj[];
    //最短路径
    private static int[] dist;
    //是否已确定最短路径
    private static boolean[] st;
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        String[] a=br.readLine().split(" ");
        int n=Integer.parseInt(a[0]);
        int m=Integer.parseInt(a[1]);
        adj=new HashMap[n];
        for(int i=0;i<n;i++){
            adj[i]=new HashMap<>();
        }
        dist=new int[n];
        Arrays.fill(dist,Integer.MAX_VALUE);
        st=new boolean[n];
        dist[0]=0;
        //邻接表初始化
        while(m-- >0){
            String[] t=br.readLine().split(" ");
            Integer i=Integer.parseInt(t[0])-1,j=Integer.parseInt(t[1])-1,w=Integer.parseInt(t[2]);
            if(i!=j){
                int v=adj[i].getOrDefault(j,Integer.MAX_VALUE);
                adj[i].put(j,v>w?w:v);
            }
        }
        //小顶堆
        PriorityQueue<Node> queue = new PriorityQueue<>(Comparator.comparingInt(o -> o.minDist));
        queue.offer(new Node(0,0));
        while(!queue.isEmpty()){
            Node node=queue.poll();
            if(!st[node.num]){
                st[node.num]=true;
                Map<Integer,Integer> map=adj[node.num];
                map.forEach((k,w) -> {
                    if(dist[k]>dist[node.num]+w){
                        dist[k] = dist[node.num] + w;
                        queue.offer(new Node(k,dist[k]));
                    }
                });
            }
        }
        if(dist[n-1]==Integer.MAX_VALUE){
            System.out.print(-1);
        }else{
            System.out.print(dist[n-1]);
        }
    }
}
class Node{
    int num;
    int minDist;
    public Node(int n,int d){
        this.num=n;
        this.minDist=d;
    }
    public void setDist(int d){
        this.minDist=d;
    }
}