Djisktra堆优化（链式前向星）

🌺本文将讲解dijsktra堆优化思路，并以c++和Java代码为例讲解“链式前向星”，文末附Java实战题目代码💧

🌷 仰望天空，妳我亦是行人.✨
🦄 个人主页——微风撞见云的博客🎐
🐳 《数据结构与算法》专栏的文章图文并茂🦕生动形象🦖简单易学！欢迎大家来踩踩~🌺
💧 《Java学习笔记》专栏的文章是本人在Java学习中总结的一些知识点~ 💐
🥣 《每天一点小知识》专栏的文章可以丰富你的知识库，滴水成河~ 🌊
🪁 希望本文能够给读者带来一定的帮助~🌸文章粗浅，敬请批评指正！🐥

文章目录

Djisktra堆优化（链式前向星）
前言
何为“链式前向星”？
堆优化dijsktra代码实现
- C++实现步骤(参考其他博主，并非本人总结)
- Java实现步骤以一道蓝桥杯模板题为例进行讲解（代码含注释）
总结

前言

朴素算法的时间复杂度是n的平方，而一般题目给的数据都是差不多le5,这时候肯定会爆

朴素dijsktra算法可以参考这位博主的文章：算法之迪杰斯特拉(dijkstra)非常详细介绍

用堆优化来降低时间复杂度
时间复杂度降到nlogn+m
堆优化了每次找离起点最近的点的时间复杂度。

何为“链式前向星”？

如果说邻接表是不好写但效率好，邻接矩阵是好写但效率低的话，前向星就是一个相对中庸的数据结构。前向星固然好写，但效率并不高。而在优化为链式前向星后，效率也得到了较大的提升。虽然说，世界上对链式前向星的使用并不是很广泛，但在不愿意写复杂的邻接表的情况下，链式前向星也是一个很优秀的数据结构。 ——摘自《百度百科》

链式前向星其实就是静态建立的邻接表;
时间效率为O（n）、空间效率也为O（n）、遍历效率也为O（n）;
对于下面的数据:第一行5个顶点、7条边。接下来是边的起点，终点和权值。如：边1 -> 2 权值为1。

链式前向星存的是以【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】
题目地址：https://www.lanqiao.cn/problems/1122/learning/
代码详解

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为起点的当前边的编号
    }

}