堆优化版 Dijkstra算法主要内容

• 一、基本思路
• • 1、基本概念
  • 2、基本原理流程
• 二、Java、C语言模板实现
• 三、例题题解

一、基本思路

1、基本概念

• 一般用于求解从 1 号点到其他点——单源最短路
• 基于贪心算法
• Si 表示当前已确定最短距离的点
• 有向图与无向图的边增加与之前一直——只需要考虑为有向图即可

2、基本原理流程

• 此处摘录来自 AcWing-小呆呆
  
  

二、Java、C语言模板实现

//Java 模板实现class PII implements Comparable{    int first;    int second;        public PII(int first, int second){        this.first = first;                 // 此处存储的是距离dis        this.second = second;               // 此处存储的是节点编号    }        public int compareTo(PII o){                        // 此处实现了Comparable接口，为了实现小根堆，按照dis进行排序        return Integer.compare(this.first, o.first);    }}    static int N = 150010;    static int INF = 0x3f3f3f3f;    static int idx = 0;    static int[] h = new int[N];    static int[] e = new int[N];    static int[] ne = new int[N];    static int[] w = new int[N];    static int[] dis = new int[N];    static boolean[] st = new boolean[N];    static int n,m;    static int a,b,c;        static void add(int a, int b, int c){        // 使用单链表，每个点下面挂着可以访问的节点        e[idx] = b;        ne[idx] = h[a];        w[idx] = c;             // 此处用的是邻接表进行边权存储，而不是邻接矩阵        h[a] = idx++;    }        static int dijkstra(){        PriorityQueue queue = new PriorityQueue();        // st表示已经确定最短距离的点        // 使用优先队列寻找  可以连接到的+未被确定距离dis（st为true就可直接略过）  的距离最小值        // queue维护当前未在st中标记过且离源点最近的点        // 然后用这个点去更新其他的点，不过只选择最小值更新                dis[1] = 0;                 // 初始化第一个节点为0        queue.add(new PII(0, 1));   // 将第一个节点加入进行其他点（可以和1链接点）的距离更新                while(!queue.isEmpty()){            PII p = queue.poll();           // 小根堆，根节点就是dis的最小值，相当于已经进行了按序依次取出            int temp = p.second;            // 这里取出的是dis最小点的节点编号            int distance = p.first;         // 这里取出的是dis最小点的dis，为了后面更新与比较                        if(st[temp] == true){                   // 如果为ture ,也就是说明这个点已经确定了最短距离                                                    // 后续只需要其他点在能连接到他的时候进行更新即可。                continue;            }else{                st[temp] = true;            }                                    for(int i = h[temp]; i != -1; i = ne[i]){       //遍历当前这个最小点能链接到的点，更新其他点的距离信息                int j = e[i];                               // 存储的是下一个点标号                if(dis[j] > dis[temp] + w[i]){              // 如果用来更新的t点+本身边权 《 dis，那就可以更新了                    dis[j] = dis[temp] + w[i];                    queue.add(new PII(dis[j], j));          // 这时候这个刚更新距离的点，也可以后面用来更新其他点                }            }                                }        if(dis[n] == INF){            return -1;        }                return dis[n];                    }

```cpp// C++语言实现，此处是yxc实现typedef pair PII;int n;      // 点的数量int h[N], w[N], e[N], ne[N], idx;       // 邻接表存储所有边int dist[N];        // 存储所有点到1号点的距离bool st[N];     // 存储每个点的最短距离是否已确定// 求1号点到n号点的最短距离，如果不存在，则返回-1int dijkstra(){    memset(dist, 0x3f, sizeof dist);    dist[1] = 0;    priority_queue, greater> heap;    heap.push({0, 1});      // first存储距离，second存储节点编号    while (heap.size())    {        auto t = heap.top();        heap.pop();        int ver = t.second, distance = t.first;        if (st[ver]) continue;        st[ver] = true;        for (int i = h[ver]; i != -1; i = ne[i])        {            int j = e[i];            if (dist[j] > distance + w[i])            {                dist[j] = distance + w[i];                heap.push({dist[j], j});            }        }    }    if (dist[n] == 0x3f3f3f3f) return -1;    return dist[n];}

三、例题题解

// java题解实现import java.util.*;public class Main{    static int N = 150010;    static int INF = 0x3f3f3f3f;    static int idx = 0;    static int[] h = new int[N];    static int[] e = new int[N];    static int[] ne = new int[N];    static int[] w = new int[N];    static int[] dis = new int[N];    static boolean[] st = new boolean[N];    static int n,m;    static int a,b,c;        static void add(int a, int b, int c){        // 使用单链表，每个点下面挂着可以访问的节点        e[idx] = b;        ne[idx] = h[a];        w[idx] = c;             // 此处用的是邻接表进行边权存储，而不是邻接矩阵        h[a] = idx++;    }        static int dijkstra(){        PriorityQueue queue = new PriorityQueue();        // st表示已经确定最短距离的点        // 使用优先队列寻找  可以连接到的+未被确定距离dis（st为true就可直接略过）  的距离最小值        // queue维护当前未在st中标记过且离源点最近的点        // 然后用这个点去更新其他的点，不过只选择最小值更新                dis[1] = 0;                 // 初始化第一个节点为0        queue.add(new PII(0, 1));   // 将第一个节点加入进行其他点（可以和1链接点）的距离更新                while(!queue.isEmpty()){            PII p = queue.poll();           // 小根堆，根节点就是dis的最小值，相当于已经进行了按序依次取出            int temp = p.second;            // 这里取出的是dis最小点的节点编号            int distance = p.first;         // 这里取出的是dis最小点的dis，为了后面更新与比较                        if(st[temp] == true){                   // 如果为ture ,也就是说明这个点已经确定了最短距离                                                    // 后续只需要其他点在能连接到他的时候进行更新即可。                continue;            }else{                st[temp] = true;            }                                    for(int i = h[temp]; i != -1; i = ne[i]){       //遍历当前这个最小点能链接到的点，更新其他点的距离信息                int j = e[i];                               // 存储的是下一个点标号                if(dis[j] > dis[temp] + w[i]){              // 如果用来更新的t点+本身边权 《 dis，那就可以更新了                    dis[j] = dis[temp] + w[i];				// 注意此处是wi，使用的是temp到j的权重wi进行更新(单链表存）                    queue.add(new PII(dis[j], j));          // 这时候这个刚更新距离的点，也可以后面用来更新其他点                }            }                                }        if(dis[n] == INF){            return -1;        }                return dis[n];                    }        public static void main(String[] args){        Scanner in = new Scanner(System.in);                n = in.nextInt();        m = in.nextInt();                for(int i = 0; i < N; i++){            h[i] = -1;            dis[i] = INF;        }                for(int i = 0; i < m; i++){            a = in.nextInt();            b = in.nextInt();            c = in.nextInt();            add(a,b,c);        }                int result = dijkstra();                System.out.println(result);            }}class PII implements Comparable{    int first;    int second;        public PII(int first, int second){        this.first = first;                 // 此处存储的是距离dis        this.second = second;               // 此处存储的是节点编号    }        public int compareTo(PII o){                        // 此处实现了Comparable接口，为了实现小根堆，按照dis进行排序        return Integer.compare(this.first, o.first);    }}