Dijkstra算法是一种典型的单源最短路径算法，用于计算从一个节点到所有其他节点的最短路径。本文将详细讲解算法的框图和实现，有需要的可以参考。
目录
实现小根桩Dijsktra测试的工作流程和总体思路简介
简介
Dijkstra算法是一种典型的单源最短路径算法，用于计算从一个节点到所有其他节点的最短路径。主要特点是从起点向外逐层扩展，直至到达终点。Dijkstra算法是一种具有代表性的最短路径算法，在数据结构、图论、运筹学等很多专业课程中都作为基础内容进行了详细的介绍。注意，该算法要求图中没有负加权边。对应问题：在一个无向图G=(V，E)中，假设每条边E(i)的长度W(i)，求从顶点V0到每个节点的最短路径。
工作过程
Dijkstra算法将顶点集分成两组。一组记录找到最短路径的顶点作为最终节点，另一组记录求解中的顶点作为过程节点。在step1:finallyNodes中，顶点在开头只有源节点，最短路径长度为0，而processNodes包含源节点以外的节点，并初始化路径长度。对与源节点直接相连的路径长度进行加权，未相连的标记为。第二步：从process中选择路径长度最短的顶点，添加finallyNodes，更新processNodes将当前顶点连接的顶点的路径长度更新为min(当前权重，当前顶点的最短路径长度，当前顶点与顶点之间连接的边的权重)。步骤3:重复步骤2，直到processNodes数组为空。
总体思路
这次我想先描述一下我的大致想法，然后再写下具体的实现。首先，为了方便，我使用邻接表存储图结构。邻接表是一个二维数组，值存储权重。根据上面工作流程描述的内容，我们会有两个中间集记录，finallyNodes记录最终结果。我们只需要把计算的结果塞进去。但是，processNodes是一个不断变化和更新的集合，其中的操作包括删除节点、更改节点值和查找节点值。同时我们每次都需要取出processNodes中记录的最小距离，所以ProcessNodes准备用最小堆来做。删除节点和更改节点值后，我们需要将堆调整到最小堆。java本身的优先级队列不提供改变节点值的操作，所以我们需要在这里实现一个小的根堆来支持上面的操作。那么dijkstra算法就可以公平的实现了。
实现
小根堆
如果不熟悉堆，可以先看这篇文章：heap(优先级队列)。这里不做过多解释，直接粘贴代码。这里堆中存储的数据是int二维数组的格式，存储节点的下标位置和对应的距离，排序是基于存储的距离。
publicclassMinHeap{
listint[][]堆；
/**
*获取和移除堆的顶部元素，并调整堆
* @返回
*/
publicint[][]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
}
/**
*确定它是否为空。
* @返回真/假
*/
publicbooleanisEmpty() {
if(null==this.heap) {
returntrue
}
if(this.heap.size()==0) {
returntrue
}
返回false；
}
/**
*修改索引位置节点的值并调整最小堆(Java priorityQueue不提供)
* @param index修改节点位置
* @param value修改值
*/
publicfoidchangevalue(int index，intvalue) {
int src=heap . get(index)[0][1]；
heap . get(index)[0][1]=value；
//直接比较当前值是大了还是小了，再考虑是上调还是下调。
//那么当前值可能会向上移动
if(srcvalue) {
this . up adjust(index)；
返回；
}
this.adjust(index，heap . size()-1)；
}
publicvidupadjust(intindex){
//依次与父节点比较，如果比父节点小就直接交换。一直到根节点。
while(index0) {
intparent=index1
//父节点本来就比当前节点小，不需要调整。
if(heap . get(parent)[0][1]=heap . get(index)[0][1]){
打破；
}
swap(索引，父)；
index=parent
}
}
/**
*初始化最小堆
* @param nums
*/
publicfoidinit(int[][]nums){
heap=new ArrayList(nums . length)；
for(inti=0；inums.lengthi ) {
int[][]temp=new int[1][2]；
temp[0][0]=nums[I][0]；
temp[0][1]=nums[I][1]；
heap . add(temp)；
}
//从最后一个父节点开始调整堆
for(inti=nums . length/2；I=0；- i) {
this.adjust(i，nums . length-1)；
}
}
/**
*从当前索引调整到最小堆。
* @param index当前节点下标
* @param end最后一个节点下标
*/
privatevidadjust(intindex，intended){
//找到当前节点的子节点，将较小的节点与当前节点交换，一路向下，直到最后
while(index=end) {
//左侧子节点
intleft=index1
if(left 1=end heap . get(left 1)[0][1]heap . get(left)[0][1]){
//查找当前较小的节点
左；
}
//没有子节点，或者当前子节点都大于当前节点，已经满足最小堆，不需要调整。
if(leftend | | heap . get(index)[0][1]=heap . get(left)[0][1]){
打破；
}
swap(索引，左)；
index=左；
}
}
privatewidswap(inti，intj) {
int[][]temp=heap . get(I)；
heap.set(i，heap . get(j))；
heap.set(j，temp)；
}
}
Dijsktra
数据结构
一个图只存储节点值，一个节点数组nodes，图中所有节点，一个二维数组adjacencyMatrix，存储图中节点之间边的权重。行和列下标对应于节点数组下标。
//节点
节点[]个节点；
//邻接矩阵
int[][]adjacency matrix；
publicclassNode{
privatecharvalue
节点(字符值){
this.value=value
}
}
初始化
初始化图values标记图中的所有节点值，edges标记图中的边，数据格式为(节点1的下标，节点2的下标，边权重)
privatevoidinitGraph(char[]值，String[]边){
nodes=new node[values . length]；
//初始化节点node
for(inti=0；ivalues.lengthi ) {
nodes[I]=new node(values[I])；
}
adjacency matrix=new int[values . length][values . length]；
//初始化邻接表，相同节点的权重记为0，不相邻节点的权重记为整数。最大值
for(inti=0；ivalues.lengthi ) {
for(intj=0；jvalues.lengthj ) {
if(i==j) {
adjacency matrix[I][j]=0；
继续；
}
adjacency matrix[I][j]=整数。MAX _ VALUE
adjacency matrix[j][I]=整数。MAX _ VALUE
}
}
//根据边更新相邻节点的权值
对于(纵梁边缘：边缘){
String[]node=edge.split('，')；
inti=integer . value of(node[0])；
intj=integer . value of(node[1])；
int weight=integer . value of(node[2])；
adjacency matrix[I][j]=权重；
adjacency matrix[j][I]=weight；
}
visited=new boolean[nodes . length]；
}
初始化dijsktra算法必要的finallyNodes和processNodes
/**
*标记对应的下标节点是否已经处理，避免二次处理。
*/
布尔[]已访问；
/**
*记录最短路径finallyNodes[0][0]，记录节点下标，finallyNodes[0][1]记录最短路径长度。
*/
listint[][]finallyNodes；
/**
*记录当前求解过程的路径长度，因为每次都取最短的已知路径，所以记录最小堆。
*但是java Priority Queue没有实现更改值，所以这里需要你自己实现。
*首先，每次取出堆顶元素后，堆顶元素加入finallyNodes。此时，需要更新与当前元素相邻的节点的路径长度。
*然后重新调整小根桩。
*首先：只会更新较小的数据，所以从较小的元素开始调整到顶部，或者直接调用adjustment方法从堆的顶部调整到底部。
*/
MinHeapprocessNodes
/**
* 初始化，主要初始化最终节点和进程节点，最终节点加入源节点，进程节点加入其他节点
* @param节点索引
*/
privatevoidinitDijkstra(intnodeIndex){
finallyNodes=新数组列表(节点。长度)；
process nodes=newMinHeap()；
int[][]node=new int[1][2]；
node[0][0]=节点索引；
node[0][1]=邻接矩阵[节点索引][节点索引]；
finallyNodes.add(节点);
已访问[节点索引]=true；
int[][]process=new int[nodes。长度-1][2]；
intj=0；
for(inti=0；索引节点。长度；i ) {
if(i==nodeIndex) {
继续；
}
process[j][0]=I；
process[j][1]=邻接矩阵[节点索引][I]；
j；
}
//初始化最小堆
流程节点。init(进程)；
}
dijsktra算法实现
publicviddijkstra(){
//1。堆顶取出最小元素，加入最终节点
//2。将与堆顶元素相连节点距离更新，
而(!processNodes.isEmpty()) {
int[][]head=流程节点。pop()；
最终节点。加(头)；
intnodeIndex=head[0][0]；
已访问[节点索引]=true；
//跟堆顶元素相邻的元素
for(intj=0；jnodes.lengthj ) {
//找到相邻节点
if(visited[j]||Integer .MAX _ VALUE==邻接矩阵[节点索引][j]){
继续；
}
for(inti=0；iprocessnodes。堆。size()；i ) {
int[][]node=流程节点。堆。get(I)；
//找到节点并且值变小，需要调整
if(node[0][0]==jnode[0][1]head[0][1]邻接矩阵[节点索引][j]){
processNodes.changeValue(i，head[0][1]邻接矩阵[节点索引][j])；
打破；
}
}
}
}
}
测试
publicstaticvoidmain(String[]args){
char[]values=newchar[]{'A '，' B '，' C '，' D '，' E '，' F '，' G '，' H ' }；
String[]edges=newString[]{'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 ' }；
dijkstradijkstra=newDijkstra()；
dijkstra.initGraph(值，边);
intstartNodeIndex=0；
迪克斯特拉。initdijkstra(startNodeIndex)；
迪克斯特拉。Dijkstra()；
for(int[][]node:Dijkstra。最终节点){
系统。出去。println(Dijkstra。节点[节点[0][0]]."价值"距离dijkstra.nodes[startNodeIndex]."价值"最短路径为：' node[0][1])；
}
}
以上就是详解Java 语言(一种计算机语言，尤用于创建网站)语言（一种计算机语言，尤用于创建网站)中迪克斯特拉（迪杰斯特拉)算法的图解与实现的详细内容，更多关于爪哇迪克斯特拉算法的资料请关注我们其它相关文章！
郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。