java dijkstra算法,java 迪杰斯特拉

　　00-1010小根桩Dijsktra试验的工作过程、总体思路及体会简介

目录

Dijkstra算法是典型的单源最短路径算法，用于计算从一个节点到所有其他节点的最短路径。主要特点是从起点向外逐层扩展，直至到达终点。Dijkstra算法是一种具有代表性的最短路径算法，在数据结构、图论、运筹学等很多专业课程中都作为基础内容进行了详细的介绍。注意，该算法要求图中没有负加权边。对应问题：在一个无向图G=(V，E)中，假设每条边E(i)的长度W(i)，求从顶点V0到每个节点的最短路径。

简介

Dijkstra算法将顶点集分为两组。一组记录找到最短路径的顶点作为最终节点，另一组记录求解中的顶点作为过程节点。在step1:finallyNodes中，顶点起初只有源节点，最短路径长度为0，而processNodes包含源节点以外的节点，并初始化路径长度。与源节点直接相连的路径长度被加权，但不相连。步骤2:从进程中选择路径长度最小的顶点，添加finallyNodes，更新processNodes，将当前顶点连接的顶点的路径长度更新为min(当前权重，当前顶点的最短路径长度，当前顶点连接的顶点的边权重)。步骤3:重复步骤2，直到processNodes数组为空。

　　00-1010这次我想先描述一下我的大致思路，然后再写具体的实现。首先，为了方便，我使用邻接表存储图结构。邻接表是一个二维数组，值存储权重。根据上面工作流程描述的内容，我们会有两个中间集记录，finallyNodes记录最终结果。我们只需要把计算的结果塞进去。但是，processNodes是一个不断变化和更新的集合，其中的操作包括删除节点、更改节点值和查找节点值。同时我们每次都需要取出processNodes中记录的最小距离，所以ProcessNodes准备用最小堆来做。删除节点和更改节点值后，我们需要将堆调整到最小堆。java本身的优先级队列不提供改变节点值的操作，所以我们需要在这里实现一个小的根堆来支持上面的操作。那么dijkstra算法就可以公平的实现了。

工作过程

　　00-1010如果不熟悉堆，可以先看这篇文章：堆(优先级队列)。这里不做过多解释，直接粘贴代码。这里堆中存储的数据是int二维数组的格式，存储节点的下标位置和对应的距离，排序是基于存储的距离。

　　public classminheap { Listint[][]堆；/* * *获取并移除堆的top元素，调整heap * @ return */public int[][]pop(){ int[][]top=heap . Get(0)；heap.set(0，heap . get(heap . size()-1))；heap . remove(heap . size()-1)；//调整堆this.adjust(0，heap . size()-1)；returntop}/* * *判断是否为空* @ return true/false */publicbooleanisEmpty(){ if(null==this . heap){ return true；} if(this . heap . size()==0){ return true；}返回false；}/* * *修改索引位置节点的值并调整最小堆(Java priorityQueue不提供)* @param index修改节点位置* @param value修改值*/publicfoidchangevalue(int index，int value){ int src=heap . get(index)[0][1]；heap . get(index)[0][1]=value；//直接比较当前值是大了还是小了，再考虑是上调还是下调。

　　         //则当前值可能往上移动           if (src > value) {               this.upAdjust(index);               return;          }           this.adjust(index, heap.size() - 1);      }       public void upAdjust(int index) {           //依次与双亲节点进行比较，小于双亲节点就直接交换。一直到根节点           while (index > 0) {               int parent = index >> 1;               //双亲节点本来小于当前节点不需要进行调整               if (heap.get(parent)[0][1] <= heap.get(index)[0][1]) {                   break;              }               swap(index, parent);               index = parent;          }      }              /**        * 初始化一个最小堆        * @param nums        */       public void init(int[][] nums) {           heap = new ArrayList<>(nums.length);           for (int i = 0 ; i < nums.length; i ++) {               int[][] temp = new int[1][2];               temp[0][0] = nums[i][0];               temp[0][1] = nums[i][1];               heap.add(temp);          }           //从最后一个双亲节点开始将堆进行调整           for (int i = nums.length / 2 ; i >= 0 ; -- i) {               this.adjust(i, nums.length - 1);          }      }       /**        * 从当前index开始调节为最小堆        * @param index 当前节点下标        * @param end 最后一个节点下标        */       private void adjust(int index, int end) {           //找到当前节点的孩子节点，将较小的节点与当前节点交换，一直往下，直至end           while (index <= end) {               //左孩子节点               int left = index << 1;               if (left + 1 <= end && heap.get(left + 1)[0][1] < heap.get(left)[0][1] ) {                   //找到当前较小的节点                   ++ left;              }               //没有孩子节点，或者当前的孩子节点均已大于当前节点，已符合最小堆，不需要进行调整               if (left > end  heap.get(index)[0][1] <= heap.get(left)[0][1]) {                   break;              }               swap(index, left);               index = left;          }      }       private void swap(int i, int j) {           int[][] temp = heap.get(i);           heap.set(i, heap.get(j));           heap.set(j, temp);      }  }

Dijsktra

数据结构

　　图节点仅存储节点值，一个Node数组nodes，存储图中所有节点，一个二维数组adjacencyMatrix，存储图中节点之间边的权重，行和列下标与nodes数组下标对应。

//节点Node[] nodes;//邻接矩阵int[][] adjacencyMatrix;public class Node {       private char value;       Node(char value) {           this.value = value;      }  }

初始化

　　初始化图values标志的图中所有节点值，edges标志图中边，数据格式为（node1的下标，node2的下标，边权重）

private void initGraph(char[] values, String[] edges) {       nodes = new Node[values.length];//初始化node节点       for (int i = 0 ; i < values.length ; i ++) {           nodes[i] = new Node(values[i]);      }       adjacencyMatrix = new int[values.length][values.length];//初始化邻接表，同一个节点权重记为0，不相邻节点权重记为Integer.MAX_VALUE       for (int i = 0 ; i < values.length ; i++) {           for (int j = 0 ; j < values.length ; j ++) {               if (i == j) {                   adjacencyMatrix[i][j] = 0;                   continue;              }               adjacencyMatrix[i][j] = Integer.MAX_VALUE;               adjacencyMatrix[j][i] = Integer.MAX_VALUE;          }      }//根据edges更新相邻节点权重值       for (String edge : edges) {           String[] node = edge.split(",");           int i = Integer.valueOf(node[0]);           int j = Integer.valueOf(node[1]);           int weight = Integer.valueOf(node[2]);           adjacencyMatrix[i][j] = weight;           adjacencyMatrix[j][i] = weight;      }       visited = new boolean[nodes.length];  }

初始化dijsktra算法必要的finallyNodes和processNodes

/*** 标志对应下标节点是否已经处理，避免二次处理*/boolean[] visited;   /**    * 记录已经求得的最短路径 finallyNodes[0][0]记录node下标，finallyNodes[0][1]记录最短路径长度    */   List<int[][]> finallyNodes;   /**    * 记录求解过程目前的路径长度，因为每次取当前已知最短，所以最小堆进行记录    * 但是java优先队列没有实现改变值，这里需要自己实现    * 首先每次取出堆顶元素之后，堆顶元素加入finallyNodes，此时需要更新与当前元素相邻节点的路径长度    * 然后重新调整小根堆    * 首先：只会更新变小的数据，所以从变小元素开始往上进行调整，或者直接调用调整方法，从堆顶往下进行调整    */   MinHeap processNodes;/**    * 初始化，主要初始化finallyNodes和processNodes，finallyNodes加入源节点，processNodes加入其他节点    * @param nodeIndex    */   private void initDijkstra(int nodeIndex) {       finallyNodes = new ArrayList<>(nodes.length);       processNodes = new MinHeap();       int[][] node = new int[1][2];       node[0][0] = nodeIndex;       node[0][1] = adjacencyMatrix[nodeIndex][nodeIndex];       finallyNodes.add(node);       visited[nodeIndex] = true;       int[][] process = new int[nodes.length - 1][2];       int j = 0;       for (int i = 0 ; i < nodes.length ; i++) {           if (i == nodeIndex) {               continue;          }           process[j][0] = i;           process[j][1] = adjacencyMatrix[nodeIndex][i];           ++ j;      }       //初始化最小堆       processNodes.init(process);  }

dijsktra算法实现

public void dijkstra() {       //1。堆顶取出最小元素，加入finallyNodes//2。将与堆顶元素相连节点距离更新，       while (!processNodes.isEmpty()) {           int[][] head = processNodes.pop();           finallyNodes.add(head);           int nodeIndex = head[0][0];           visited[nodeIndex] = true;           //跟堆顶元素相邻的元素           for (int j = 0 ; j < nodes.length ; j ++) {               //找到相邻节点               if (visited[j]  Integer.MAX_VALUE == adjacencyMatrix[nodeIndex][j]) {                   continue;              }               for (int i = 0 ; i < processNodes.heap.size() ; i++) {                   int[][] node = processNodes.heap.get(i);                   //找到节点并且值变小，需要调整                   if (node[0][0] == j && node[0][1] > head[0][1] + adjacencyMatrix[nodeIndex][j]) {                       processNodes.changeValue(i, head[0][1] + adjacencyMatrix[nodeIndex][j]);                       break;                  }              }          }      }  }

测试

public static void main(String[] args) {       char[] values = new char[]{A,B,C,D,E,F,G,H};       String[] edges = new String[]{"0,1,2","0,2,3","0,3,4","1,4,6","2,4,3","3,4,1","4,5,1","4,6,4","5,7,2","6,7,2"};       Dijkstra dijkstra = new Dijkstra();       dijkstra.initGraph(values, edges);       int startNodeIndex = 0;       dijkstra.initDijkstra(startNodeIndex);       dijkstra.dijkstra();       for (int[][] node : dijkstra.finallyNodes) {           System.out.println(dijkstra.nodes[node[0][0]].value + "距离" + dijkstra.nodes[startNodeIndex].value + "最短路径为：" + node[0][1]);      }  }

　　以上就是详解Java中Dijkstra(迪杰斯特拉)算法的图解与实现的详细内容，更多关于Java Dijkstra算法的资料请关注盛行IT其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。