基于二叉堆优化的迪杰斯特拉算法

本文主要是介绍基于二叉堆优化的迪杰斯特拉算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前言介绍

迪杰斯特拉(Dijkstra)算法是1959年由荷兰计算机科学家Dijkstra提出的算法，用于在加权图中计算从单个源点到其余节点的最短距离。采用贪心策略，每次选取到源点最近且未被访问的节点，遍历它的邻居节点更新它们到源点的最短距离，直到扩展完成。

算法诞生

在迪杰斯特拉算法出现，有这样一个问题：在荷兰的任意选取两个城市，它们的最短距离是多少？在当时，这个问题最好的算法运行时间随着城市规模呈立方增长，而迪杰斯特拉的算法运行时间只会随着城市规模呈平方增长。有趣的是，这个算法是他和未婚妻Maria C. Debets在一个咖啡馆露台喝咖啡的时候，花了二十分钟想出来的。直到今天他的算法还被广泛应用，比如交通路线规划、网络路由等等。此段部分摘自26岁发明最短路径算法，47岁斩获图灵奖。

迪杰斯特拉算法

原始算法

原始的迪杰斯特拉算法步骤大致分为以下几个步骤：

1.初始化距离数组和访问数组(bool类型)，并置源点位置为0；

2.遍历选择离源点最近且未被访问的顶点，置其为被访问；

3.依次遍历它的邻居节点并尝试更新与源点的最短距离；

4.直到所有节点遍历结束，扩展完成。

上述过程的java代码如下：

    public int[] dijkstra(int[][] adj,int source){int n=adj.length;int[] shortest = new int[n];Arrays.fill(shortest,Integer.MAX_VALUE/2);shortest[source]=0;boolean[] visited = new boolean[n];for(int i=0;i<n;i++){int k=-1;for(int j=0;j<n;j++){if(!visited[j]&&(k==-1||shortest[j]<shortest[k]))k=j;}visited[k]=true;for(int m=0;m<n;m++){if(adj[k][m]!=Integer.MAX_VALUE&&shortest[k]+adj[k][m]<shortest[m])shortest[m]=shortest[k]+adj[k][m];}}return shortest;}

原始算法的时间复杂度为O(V^2)，空间复杂度为O(V^2)，其中V为节点个数。我们可以发现，该算法需要开辟O(V^2)的空间来存储图的信息，并且时间复杂度也是平方级别的，所以它处理小规模图的时候够用，但是在处理大规模节点的时候，空间会溢出，时间上也会超时。因此在节点较多的情况下，原始算法不再适用，所以考虑使用一些数据结构来进行优化。

二叉堆优化

考虑这样一种场景，一个图的节点数是一个大值V，而图中的边E远小于V^2，那么我们在存储图的时候完全可以不用邻接矩阵而是邻接表，可以节省大量空间，并且我们在寻找距离源点最近的节点的时候，原始做法是遍历一遍数组，这边可以使用小根堆的方式来实现，调整的时间复杂度只有log(V)级别，这样我们就描述完了对原始算法的优化点，具体流程可以是这样：

1.初始化距离数组和访问数组(bool类型)，读取边并构造图的邻接表；

2.初始化一个小根堆实现的优先级队列，初始的源节点入队，距离源节点的长度为0；

3.队列不为空时，每次弹出一个元素，得到该节点和对应的最短距离，置访问数组对应位置为true，并尝试更新它的邻居节点的当前最短距离；

4.重复操作3，结束之后距离数组中的对应位置存储的值即为各个节点到达源点的最短距离。

上述过程的java代码如下：

public static void main(String[] args) {Scanner scanner = new Scanner(System.in);int n = scanner.nextInt();//节点个数int e=scanner.nextInt();//边个数for(int i=0;i<N;i++){graphAdj[i]=new ArrayList<>();}for(int i=0;i<e;i++){int u = scanner.nextInt();int v = scanner.nextInt();int w = scanner.nextInt();addEdge(u,v,w);}dijkstra(0);//shortest中0到n-1元素即为到源点0的最短距离。}static int N=100010;static List<Edge>[] graphAdj=new ArrayList[N];static int[] shortest=new int[N];static boolean[] visited=new boolean[N];static class Edge{int to;int weight;Edge(int to,int weight){this.to=to;this.weight=weight;}}public static void dijkstra(int source){PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(new Comparator<int[]>() {@Overridepublic int compare(int[] o1, int[] o2) {return o1[1]-o2[1];}});priorityQueue.offer(new int[]{source,0});Arrays.fill(shortest,Integer.MAX_VALUE);shortest[source]=0;while (!priorityQueue.isEmpty()){int[] poll = priorityQueue.poll();int node=poll[0];int distance=poll[1];if(visited[node])continue;visited[node]=true;for(Edge edge:graphAdj[node]){int to = edge.to;int weight = edge.weight;if(distance+weight<shortest[to]){shortest[to]=distance+weight;priorityQueue.offer(new int[]{to,shortest[to]});}}}}public static void addEdge(int u,int v,int w){graphAdj[u].add(new Edge(v,w));graphAdj[v].add(new Edge(u,w));}

代码方面我写的比较完善，所以看上去比原始算法更长，只要多了个构造内部类Edge和添加边的逻辑，然后核心思想在dijkstra(int source)方法中体现，为了应对更大的图，我们直接初始化的时候将N设置的比较大。