堆优化版Dijkstra求最短路-java

主要通过堆优化Dijkstra算法解决最短路，可以跟朴素版的Dijkstra算法进行对比。

文章目录

前言

主要通过堆优化Dijkstra算法解决最短路，可以跟朴素版的Dijkstra算法进行对比。

提示：以下是本篇文章正文内容，下面案例可供参考

一、Dijkstra求最短路

给定一个 n 个点 m 条边的有向图，图中可能存在重边和自环，所有边权均为非负值。

请你求出 1 号点到 n 号点的最短距离，如果无法从 1 号点走到 n 号点，则输出 −1。

输入格式

第一行包含整数 n 和 m。

接下来 m 行每行包含三个整数 x,y,z，表示存在一条从点 x 到点 y 的有向边，边长为 z。

输出格式

输出一个整数，表示 1 号点到 n 号点的最短距离。

如果路径不存在，则输出 −1。

数据范围

1≤n,m≤1.5×100000,
图中涉及边长均不小于 0，且不超过 10000。
数据保证：如果最短路存在，则最短路的长度不超过 1000000000。

输入样例：

3 3
1 2 2
2 3 1
1 3 4

输出样例：

3

二、算法思路

1.邻接表存储图

图1.1邻接表示例图 

我们引入一维整型数组head，来表示与下标i对应相连的每个结点，也就是说head数组中的每个值都是单链表的头结点；一维整型数组e用来存储新结点即结点的编号；整型index用来表示新结点在e数组中的下标；一维整型数组ne用来存储当前节点指向的下一个结点在e数组中的下标；再引入一维整型数组w来存储每条边的权重。

添加边，我们采用头插法，例如a b c即a指向b的边且边得权重为c；我们只需在下标为a的单链表中插入值为b的结点并存储权重即可。我们采用头插法。第一步创建一个新结点即e[index] = b和存储权重即w[index] = c；然后将原本在head数组中下标为a的单链表连接到新结点后面即ne[index] = head[a]；再将头结点指向新结点head[a] = index；最后让index++，保证一直是在e数组中新创建的结点的下标。（注：head数组初始化全为-1表示单链表为空）

 数组模拟单链表基本操作博客

    //添加边public static void add(int a, int b, int c){e[index] = b;w[index] = c;ne[index] = head[a];head[a] = index++;}

 2.用小根堆优化Dijkstra

整体过程跟广度优先搜索得过程类似。我们引入一维整型数组dist来存储从起点到达每个点得最短距离；一维布尔类型数组，用来表示该点是否已经得到了从起点点到该点得最短距离；初始化一个小根堆heap，存储类型Pill有两个值分别是起始点到该点得最短距离和该点在e数组中的索引且小根堆判断的依据是起始点到该点的距离；然后我们还是将起点放入heap，然后进入循环当堆中元素不为空时，就弹出小根堆的根结点（离起始点最近的点）p，然后如果该点没被处理，遍历与该点相连的点j，我们用起点直接到该点的距离dist[j]和和上一个离起点最近的点加上到该点的距离即 p.dist + w[i]进行比较，如果dist[j]偏大，那么我们就要更新dist数组中的值，重复上述操作。

如果从起点到最后一个结点n的最短距离dist[n]等于dist数组的初始值，就说明没有路径从起点到达n号点的路径，输出-1；如果不等于dist数组的初始值，那么就说明有最短路径即dist[n]。

可以跟朴素版的Dijkstra算法对比着看。朴素版Dijkstra 博客

三、代码如下 

1.代码如下（示例）：

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;public class Main {static PrintWriter pw = new PrintWriter(new OutputStreamWriter(System.out));static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));static StreamTokenizer st = new StreamTokenizer(br);static int N = 10000100;//邻接表，表示以结点为i的每一个链表static int[] head = new int[N];//记录是每一个结点static int[] e = new int[N];//记录权重static int[] w = new int[N];//记录e[i]结点的下一个结点的索引static int[] ne = new int[N];//新结点的索引static int index;static int[] dist = new int[N];static boolean[] flag = new boolean[N];static int n,m;public static void main(String[] args)throws Exception {//初始化头结点Arrays.fill(head,-1);n = nextInt();m = nextInt();while (m-- > 0){int a = nextInt();int b = nextInt();int c = nextInt();//邻接表存储稀疏图add(a,b,c);}int result = Dijkstra();pw.println(result);pw.flush();}public static int Dijkstra(){Arrays.fill(dist,0x3f3f3f3f);dist[1] = 0;//优先队列实现小根堆PriorityQueue<Pill> heap = new PriorityQueue<>((a,b)->{return a.dist-b.dist;});heap.add(new Pill(0,1));while (heap.size() != 0){Pill p = heap.poll();int temp = p.index;int distance = p.dist;if(flag[temp]){continue;}flag[temp] = true;for(int i = head[temp];i != -1;i = ne[i]){int j = e[i];if (dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.offer(new Pill(dist[j],j));}}}if(dist[n] == 0x3f3f3f3f){return -1;}return dist[n];}//添加边public static void add(int a, int b, int c){e[index] = b;w[index] = c;ne[index] = head[a];head[a] = index++;}public static int nextInt() throws Exception {st.nextToken();return (int) st.nval;}public static String nextLine() throws Exception {return br.readLine();}
}
class Pill{int dist;int index;public Pill(int dist, int index){this.dist = dist;this.index = index;}}

2.读入数据

3 3
1 2 2
2 3 1
1 3 4

3.代码运行结果

3

总结

主要理解一下各个数组变量的含义，大致流程和BFS过程基本相似。