Java实现Dijkstra算法：从图结构构建到最短路径计算的全流程详解

迪杰斯特拉(Dijkstra)算法作为图论中的经典最短路径算法，自1956年提出以来，在路由算法、导航系统、网络优化等领域发挥着核心作用。本文ZHANID工具网将以Java语言为载体，系统阐述从图的抽象建模到算法实现的全流程，包含完整代码实现、复杂度分析及实际案例验证，帮助开发者深入理解算法原理并掌握工程化实现技巧。

一、算法核心原理与适用场景

1.1 算法本质

Dijkstra算法通过贪心策略逐步扩展已知最短路径的顶点集合，最终求得从起点到所有其他顶点的最短路径。其核心步骤包括：

1. 初始化：设置起点距离为0，其余顶点距离为无穷大

2. 顶点选择：每次从未处理的顶点中选择距离最小的顶点

3. 距离更新：通过选中的顶点更新其邻接顶点的距离值

4. 终止条件：所有顶点均被处理或目标顶点被选中

1.2 适用条件

1.3 时间复杂度对比

本文实现：采用二叉堆优化版本，平衡实现复杂度与运行效率

二、图的抽象建模与Java实现

2.1 图的表示方法

Java中图的表示主要有三种方式：

推荐方案：对于Dijkstra算法，邻接表结合优先队列的实现效率最优

2.2 Java类设计

//顶点类
classVertex{
Stringname;//顶点标识
intid;//唯一ID
//构造方法、getter/setter省略...
}

//边类（带权）
classEdge{
intsource;//起点ID
intdestination;//终点ID
intweight;//边权重

publicEdge(ints,intd,intw){
this.source=s;
this.destination=d;
this.weight=w;
}
}

//图类
classGraph{
privateListvertices;//顶点集合
privateListedges;//边集合
privateMapadjacencyList;//邻接表

publicGraph(){
vertices=newArrayList();
edges=newArrayList();
adjacencyList=newHashMap();
}
//其他方法...
}

2.3 图的构建方法

//添加顶点
publicvoidaddVertex(Vertexvertex){
vertices.add(vertex);
adjacencyList.put(vertex.getId(),newArrayList());
}

//添加边（无向图需添加双向边）
publicvoidaddEdge(intsrc,intdest,intweight){
Edgeedge=newEdge(src,dest,weight);
edges.add(edge);
adjacencyList.get(src).add(edge);
//如果是无向图，添加反向边
//adjacencyList.get(dest).add(newEdge(dest,src,weight));
}

//构建示例图
publicstaticGraphcreateSampleGraph(){
Graphgraph=newGraph();
//添加顶点
graph.addVertex(newVertex("A",0));
graph.addVertex(newVertex("B",1));
graph.addVertex(newVertex("C",2));
graph.addVertex(newVertex("D",3));
//添加边
graph.addEdge(0,1,4);//A->B权重4
graph.addEdge(0,2,1);//A->C权重1
graph.addEdge(1,3,1);//B->D权重1
graph.addEdge(2,1,2);//C->B权重2
graph.addEdge(2,3,5);//C->D权重5
returngraph;
}

三、Dijkstra算法核心实现

3.1 算法步骤分解

1. 初始化距离数组：dist[]，起点设为0，其余设为无穷大

2. 优先队列：存储待处理顶点，按距离排序

3. 处理循环：

• 取出距离最小的顶点u

• 遍历u的所有邻接顶点v

• 如果通过u到v的路径更短，则更新距离并调整队列

3.2 Java完整实现

importjava.util.*;

publicclassDijkstraAlgorithm{

//主方法
publicstaticvoiddijkstra(Graphgraph,intstartVertex){
intV=graph.getVertices().size();

//距离数组
int[]dist=newint[V];
Arrays.fill(dist,Integer.MAX_VALUE);
dist[startVertex]=0;

//优先队列（最小堆）
PriorityQueuepq=newPriorityQueue(Comparator.comparingInt(node->node.distance));
pq.add(newNode(startVertex,0));

//前驱节点数组（用于重建路径）
int[]prev=newint[V];
Arrays.fill(prev,-1);

while(!pq.isEmpty()){
NodecurrentNode=pq.poll();
intu=currentNode.vertex;

//遍历邻接边
for(Edgeedge:graph.getAdjacencyList().get(u)){
intv=edge.getDestination();
intnewDist=dist[u]+edge.getWeight();

//松弛操作
if(newDistB
				C
				1
				A->C
				D
				4
				A->C->B->D
实际输出：
顶点距离路径
A0V0
B3V0->V2->V1
C1V0->V2
D4V0->V2->V1->V3

	4.2 性能测试数据
测试环境：

• JDK 11

• MacBook Pro (M1 Pro, 16GB RAM)

测试结果：

结论：

• 算法时间复杂度与理论值吻合

• 适合处理中等规模图（V