Djisktra堆优化（链式前向星）
🌺本文将讲解dijsktra堆优化思路，并以c++和Java代码为例讲解“链式前向星”，文末附Java实战题目代码💧
前言
朴素算法的时间复杂度是n的平方，而一般题目给的数据都是差不多le5,这时候肯定会爆
朴素dijsktra算法可以参考这位博主的文章：算法之迪杰斯特拉(dijkstra)非常详细介绍
用堆优化来降低时间复杂度
时间复杂度降到nlogn+m
堆优化了每次找离起点最近的点的时间复杂度。
何为“链式前向星”？
如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》
链式前向星其实就是静态建立的邻接表;
时间效率为O（n）、空间效率也为O（n）、遍历效率也为O（n）;
对于下面的数据:第一行5个顶点、7条边。接下来是边的起点，终点和权值。如：边1 -> 2 权值为1。
5 7 1 2 1 2 3 2 3 4 3 1 3 4 4 1 5 1 5 6 4 5 7
链式前向星存的是以【1，n】为起点的边的集合，对于上面的数据输出就是：
1 //以1为起点的边的集合 1 5 6 1 3 4 1 2 1 2 //以2为起点的边的集合 2 3 2 3 //以3为起点的边的集合 3 4 3 4 //以4为起点的边的集合 4 5 7 4 1 5 5 //以5为起点的边不存在
我们先对上面的7条边进行编号第一条边是0以此类推编号【0~6】。
然后我们要知道两个变量的含义：
Next，表示与这个边起点相同的上一条边的编号。
head[ i ]数组，表示以 i 为起点的最后一条边的编号。
head数组一般初始化为-1， 为什么是 -1后面会讲到。加边函数是这样的：
//c++版本 void add_edge(int u, int v, int w)//加边，u起点，v终点，w边权 { edge[cnt].to = v; //终点 edge[cnt].w = w; //权值 edge[cnt].next = head[u];//以u为起点上一条边的编号，也就是与这个边起点相同的上一条边的编号 head[u] = cnt++;//更新以u为起点上一条边的编号 }
//java版本 static int total = 0;//++total：记录从第一条边到最后一条边 private static void add(int start, int end, long weight) {//链式前向星的创建方法 ends[total] = end; weights[total] = weight; next[total] = head[start];//以start为起点的上一条边的编号，即：与这个边起点相同的上一条边的编号 head[start] = total++;//更新以start为起点的上一条边的编号 }
我们只要知道next，head数组表示的含义，根据上面的数据就可以写出下面的过程：
对于1 2 1这条边：end[0] = 2; next [0] = -1; head[1] = 0;
对于2 3 2这条边：end[1]= 3; next [1]= -1; head[2] = 1;
对于3 4 3这条边：end[2] = 4; next [2]= -1; head[3] = 2;
对于1 3 4这条边：end[3] = 3; next [3]= 0; head[1] = 3;
对于4 1 5这条边：end[4] = 1; next [4]= -1; head[4] = 4;
对于1 5 6这条边：end[5] = 5; next [5]= 3; head[1] = 5;
对于4 5 7这条边：end[6] = 5; next [6]= 4; head[4] = 6;
遍历函数是这样的：
//c++版本 for(int i = 1; i <= n; i++)//n个起点 { cout << i << endl; for(int j = head[i]; j != -1; j = edge[j].next)//遍历以i为起点的边 { cout << i << " " << edge[j].to << " " << edge[j].w << endl; } cout << endl; }
//java版本 static int[] head;//表示以 i 为起点的最后一条边的编号 static int[] next;//存储与当前边起点相同的上一条边的编号 static int[] ends;//存储边的终点 static long[] weights;//权值 //链式前向星的遍历方法，遍历出以x为起点的所有边 for (int i = head[x]; i != -1; i = next[i]) {//i表示：第 i 条边 System.out.println(i + "这条边的终点：" + ends[i] + "这条边的权值：" + weights[i]); }
第一层for循环是找每一个点，依次遍历以【1，n】为起点的边的集合。第二层for循环是遍历以 i 为起点的所有边，k首先等于head[ i ]，注意head[ i ]中存的是以 i 为起点的最后一条边的编号。然后通过next[ j ]来找下一条边的编号。我们初始化head为-1，所以找到你最后一个边（也就是以 i 为起点的第一条边）时，你的next[ j ]为 -1作为终止条件。
堆优化dijsktra代码实现
C++实现步骤(参考其他博主，并非本人总结)
priority_queue默认的是大根堆
priority_queue支持小根堆的一种方法
priority_queue<int,vector<int>,greater<int>> q;
可以看到，我们把距离放在pair对的第一个，把对应的点放在pair对的第二个，这是因为小根堆的比较对象是pair对的第一个元素
而我们正是要对距离排序，把离起点最近的距离放在堆顶
算法思路：
1.链式前向星存边
2.采用优先队列和c++中的二元组pair，它相当于一个包含两个变量的结构体，所以这里也可以用结构体实现，使用重载运算符（结构体的内嵌比较函数）,但是我不太会，所以就没用
3.每次离原点最近的点都放在堆顶，并且用vis数组记录访问过的点，防止来回兜圈
4.弹出堆顶，搜索堆顶的所有连边，如果从起点到v的距离大于从从起点到u的距离+从u到v的距离，那么就更新最小距离，把它对应的点和距离加入队列
5.遍历，输出值即可
代码实现：
#include<bits/stdc++.h> #define inf 0x3f3f3f3f using namespace std; const int maxn = 2e5; struct node { int v,next,w; }edge[maxn]; int cnt; bool vis[maxn]; int dis[maxn],head[maxn]; void add(int u,int v,int w)//起点，终点，距离,链式前向星建图 { edge[cnt].w=w; edge[cnt].v=v; edge[cnt].next=head[u]; head[u]=cnt++; } void dijkstra(int n) { priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>q; memset(dis,inf,sizeof dis); q.push({0,1}); dis[1]=0; while(!q.empty()) { pair<int,int> temp = q.top();//记录堆顶，即堆内最小的边并将其弹出 q.pop(); int u = temp.second;//点 if(vis[u]) continue;//如果被访问过，就跳过 vis[u]=true;//标记 for(int i = head[u];i!=-1;i=edge[i].next)//搜索堆顶的所有连边 { int v = edge[i].v; if(dis[v]>dis[u]+edge[i].w)//松弛操作 { dis[v]=dis[u]+edge[i].w; q.push({dis[v],v});//把新遍历的点加到堆中 } } } //if(dis[n]==inf) cout<<-1<<endl; //else cout<<dis[n]<<endl; for(int i=1;i<=n;i++) cout<<dis[i]<<endl; } int main() { int n,m,u,v,w; cin>>n>>m; memset(head,-1,sizeof(head)); for(int i = 0;i<m;i++) { cin>>u>>v>>w; add(u,v,w); } dijkstra(n); return 0; } /* 测试数据 6 9 1 2 1 1 3 12 2 3 9 2 4 3 3 5 5 4 3 4 4 5 13 4 6 15 5 6 4*/
Java实现步骤 以一道蓝桥杯模板题为例进行讲解（代码含注释）
题目：蓝桥王国 【dijsktra】
代码详解
import java.util.*; public class Main { static int[] head, next, ends; static long[] weights, dis;//权值和结果集 static int n, m, total;//n个顶点，m条边，++total：从第一条边到最后一条边 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); n = scanner.nextInt(); m = scanner.nextInt(); head = new int[m + 1];//表示以 i 为起点的最后一条边的编号 next = new int[m + 1];//存储与当前边起点相同的上一条边的编号 ends = new int[m + 1];//存储边的终点 weights = new long[m + 1];//存储边的权值 dis = new long[n + 1];//存储最终结果 Arrays.fill(head, -1);//初始化 for (int i = 0; i < m; i++) { int start = scanner.nextInt(); int end = scanner.nextInt(); long weight = scanner.nextLong(); add(start, end, weight); } dijkstra(1); for (int i = 1; i <= n; i++) if (dis[i] == Long.MAX_VALUE) System.out.print(-1 + " "); else System.out.print(dis[i] + " "); } private static void dijkstra(int startPoint) { for (int i = 1; i <= n; i++) { dis[i] = Long.MAX_VALUE;//初始化时，应当赋上最坏的情况 } Queue<Node> queue = new PriorityQueue<>((o1, o2) -> (int) (o1.dis - o2.dis)); queue.offer(new Node(startPoint, weights[startPoint])); dis[startPoint] = 0;//起始位置，应当赋上最好的情况 while (!queue.isEmpty()) { Node x = queue.poll();//当前点 //链式前向星的遍历方法，遍历出以x为起点的所有边 for (int i = head[x.num]; i != -1; i = next[i]) {//i表示：第 i 条边 int j = ends[i];//第 i 条边的终点 if (dis[j] > dis[x.num] + weights[i]) {//如果length(起点-->终点) > length(起点 --> 当前点) + length(当前点 --> 终点) dis[j] = dis[x.num] + weights[i];//更新起点到终点的最短距离 queue.offer(new Node(j, dis[j]));//并将这个终点入队，以便之后通过该点访问其他顶点 } } } } static class Node { int num; long dis; public Node(int num, long dis) { this.num = num; this.dis = dis; } } private static void add(int start, int end, long weight) {//链式前向星的创建方法 ends[total] = end; weights[total] = weight; next[total] = head[start];//以start为起点的上一条边的编号，即：与这个边起点相同的上一条边的编号 head[start] = total++;//更新以start为起点的当前边的编号 } }
总结
堆优化可以有效降低朴素dijsktra的时间复杂度，OI必备，希望大家仔细理解后将其掌握。
