在计算机科学和网络工程领域，图的最短路径问题是研究如何找到从一个节点到另一个节点的最短路径的常见问题。这个问题的解决方案不仅适用于地图导航和路径规划，还广泛应用于电信网络、社交网络分析、供应链管理等多个领域。Dijkstra算法作为解决单源最短路径问题的经典算法，由荷兰计算机科学家艾兹赫尔·戴克斯特拉(Edsger W. Dijkstra)在1956年首次提出，至今仍是图论中最重要且实用的算法之一。
Dijkstra算法的主要特点是以起始点为中心向外层层扩展（广度优先搜索思想），采用贪心策略，每次遍历到始点距离最近且未访问过的顶点的邻接节点，直到扩展到终点为止。本文将全面介绍Dijkstra算法的原理、实现细节，并提供完整的Java代码实现。
Dijkstra算法适用于带权重的有向图或无向图中寻找单源最短路径的问题，但要求图中不能有负权重的边，因为负权重边可能导致算法无法找到真正的最短路径。在现实应用中，路径的权重可以代表距离、时间、成本等不同度量标准。
算法的核心思想是：每次选取一个离出发点最近且未标记的节点，调整出发点到以这个节点为中心的周边节点的最短距离。这个过程持续n-1次（n为节点数量），直到所有节点都遍历完毕。
在图论中，图由顶点（节点）和边（连接节点的线）组成，它可以是有向的也可以是无向的，可以有权重也可以没有权重。为了描述Dijkstra算法，我们需要理解几个关键的图论概念：
最短路径问题可以形式化为以下数学模型：给定一个有向图G=(V,E)，其中V是顶点集合，E是边集合，每条边(u,v)有一个权重w(u,v)。对于图中的一个特定顶点s（源点），最短路径问题要求找出从s到图中所有其他顶点v的最短路径长度d(v)。
初始化是Dijkstra算法的第一步，它的目的是确定起点，并将所有其他顶点的最短路径估计值设置为无穷大（表示尚未找到路径）。
java// 初始化距离数组
Arrays.fill(dist, 0x3f3f); // 所有节点初始距离为无穷大
dist[start] = 0; // 起点到自身距离为0
// 初始化访问标记数组
boolean[] visited = new boolean[n+1]; // 标记节点是否已确定最短路径
这里0x3f3f是一个足够大的值（16191），用于表示两个节点之间没有直接连边。选择这个值的考虑是：它足够大以避免被实际边权覆盖，同时又方便判断不可达情况（如dist[n] == 0x3f3f）。
Dijkstra算法的主循环执行n次，每次确定一个节点的最短路径：
javafor (int i = 1; i <= n; i++) { // 迭代n次（每次确定一个节点的最短路径）
int t = -1;
// 找到未确定最短路径的节点中距离最小的
for (int j = 1; j <= n; j++) {
if (!visited[j] && (t == -1 || dist[t] > dist[j])) {
t = j;
}
}
visited[t] = true; // 标记该节点已确定最短路径
这部分代码体现了算法的贪心策略：每次选择未访问节点中距离最小的节点t，认为此时dist[t]已经是最终最短距离。
在确定节点t的最短路径后，算法通过t更新其他节点的距离：
java // 通过节点t更新其他节点的距离
for (int j = 1; j <= n; j++) {
dist[j] = Math.min(dist[j], dist[t] + graph[t][j]);
}
}
这一步骤称为松弛操作，它比较其他节点在不通过新加入的节点t到达源节点的路径长度与通过t到达源节点的路径长度哪一个更小，从而选择更小的。如果通过t到达j的路径比当前已知路径更短，则更新dist[j]。
算法结束后，dist数组中存储的就是源点到所有其他节点的最短距离：
java// 输出结果
for (int i = 1; i <= n; i++) {
System.out.println("从节点" + start + "到节点" + i + "的最短距离为: " + dist[i]);
}
如果某个节点的距离仍然是初始的0x3f3f，则表示该节点不可达。
以下是基于邻接矩阵的朴素Dijkstra算法完整实现，适合稠密图（边数接近顶点数的平方）的情况，时间复杂度为O(n²)：
javaimport java.util.Arrays;
public class DijkstraAlgorithm {
private static final int INF = 0x3f3f3f3f; // 表示无穷大
public static void dijkstra(int[][] graph, int start) {
int n = graph.length - 1; // 节点编号从1开始
int[] dist = new int[n + 1]; // 存储起点到各点的最短距离
boolean[] visited = new boolean[n + 1]; // 标记是否已找到最短路径
Arrays.fill(dist, INF);
dist[start] = 0;
for (int i = 1; i <= n; i++) {
int t = -1;
// 找出未访问节点中距离最小的
for (int j = 1; j <= n; j++) {
if (!visited[j] && (t == -1 || dist[j] < dist[t])) {
t = j;
}
}
visited[t] = true;
// 更新其他节点的距离
for (int j = 1; j <= n; j++) {
dist[j] = Math.min(dist[j], dist[t] + graph[t][j]);
}
}
// 输出结果
for (int i = 1; i <= n; i++) {
System.out.println("从节点" + start + "到节点" + i + "的最短距离为: " +
(dist[i] == INF ? "不可达" : dist[i]));
}
}
public static void main(String[] args) {
// 示例图的邻接矩阵表示
int[][] graph = {
{0, 0, 0, 0, 0},
{0, 0, 2, 6, INF},
{0, INF, 0, 3, INF},
{0, INF, INF, 0, 1},
{0, INF, INF, INF, 0}
};
dijkstra(graph, 1); // 计算从节点1出发的最短路径
}
}
对于稀疏图（边数远小于顶点数的平方），可以使用优先队列（最小堆）优化，将时间复杂度降低到O(mlogn)，其中m是边数，n是顶点数：
javaimport java.util.*;
public class DijkstraHeapOptimized {
private static final int INF = 0x3f3f3f3f;
static class Edge {
int to;
int weight;
Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
static class Node implements Comparable<Node> {
int id;
int dist;
Node(int id, int dist) {
this.id = id;
this.dist = dist;
}
@Override
public int compareTo(Node other) {
return Integer.compare(this.dist, other.dist);
}
}
public static void dijkstra(List<List<Edge>> graph, int start) {
int n = graph.size() - 1;
int[] dist = new int[n + 1];
Arrays.fill(dist, INF);
dist[start] = 0;
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(start, 0));
while (!pq.isEmpty()) {
Node node = pq.poll();
int u = node.id;
if (node.dist > dist[u]) continue;
for (Edge edge : graph.get(u)) {
int v = edge.to;
int newDist = dist[u] + edge.weight;
if (newDist < dist[v]) {
dist[v] = newDist;
pq.offer(new Node(v, newDist));
}
}
}
// 输出结果
for (int i = 1; i <= n; i++) {
System.out.println("从节点" + start + "到节点" + i + "的最短距离为: " +
(dist[i] == INF ? "不可达" : dist[i]));
}
}
public static void main(String[] args) {
// 示例图的邻接表表示
int n = 4;
List<List<Edge>> graph = new ArrayList<>();
for (int i = 0; i <= n; i++) {
graph.add(new ArrayList<>());
}
// 添加边
graph.get(1).add(new Edge(2, 2));
graph.get(1).add(new Edge(3, 6));
graph.get(2).add(new Edge(3, 3));
graph.get(3).add(new Edge(4, 1));
dijkstra(graph, 1);
}
}
堆优化版使用邻接表存储图结构，更适合边数较少的情况。它通过优先队列快速获取当前距离最小的节点，避免了朴素版中线性扫描寻找最小距离节点的开销。
为了更好地理解Dijkstra算法的工作过程，让我们通过一个具体例子逐步跟踪算法的执行。
假设我们有如下有向图（节点从1开始编号）：
节点1到节点2的边权重为8 节点1到节点3的边权重为1 节点1到节点4的边权重为4 节点2到节点5的边权重为5 节点3到节点2的边权重为7 节点3到节点4的边权重为2 节点4到节点5的边权重为3
初始时，我们设置：
更新后dist: [0, 8, 1, 3, ∞]
更新后dist: [0, 8, 1, 3, 6]
dist保持不变: [0, 8, 1, 3, 6]
算法结束，最终dist数组为[0, 8, 1, 3, 6]，表示：
Dijkstra算法在现实世界中有广泛的应用：
我曾经参与过一个需要优化城市公交线路规划的项目。城市地图可以抽象成一个图，路口是节点，道路是边，边上的权重代表道路长度或行驶时间。我们最初尝试了一些简单的算法，但效果都不理想，尤其是在处理复杂的交通路况时，经常出现计算结果不准确的情况。最终，我们采用了Dijkstra算法，并取得了显著的改进。
数据结构选择：
优先队列实现：
无穷大值的设置：
0x3f3f3f3f（约10^9）能满足大多数情况提前终止优化：
双向Dijkstra搜索：
Dijkstra算法同样适用于无向图。在代码实现时，只需在添加边时同时处理两个方向的边即可：
java// 无向图处理 - 同时更新两个方向的边
graph.get(u).add(new Edge(v, weight));
graph.get(v).add(new Edge(u, weight));
在输入边时，只保留权重最小的边：
java// 处理重边，保留最小边权
g[u][v] = Math.min(g[u][v], weight);
g[v][u] = Math.min(g[v][u], weight); // 如果是无向图
Dijkstra算法的贪心策略基于一个假设：当前未访问节点中距离最小的节点的距离不会再被更新。但当图中存在负权边时，这个假设不成立，因为后续可能会通过负权边找到更短的路径。
例如，考虑下图：
A --2--> B --(-3)--> C \ / \----1-------/
从A到C的最短路径应该是A→B→C（总权重2-3=-1），但Dijkstra会先确定A到B的最短距离为2，然后确定A到C的最短距离为1，忽略了通过负权边可以得到的更短路径。
对于包含负权边的图，可以使用Bellman-Ford算法或SPFA算法。
算法结束后，检查终点的距离是否仍为初始的无穷大值：
javaif (dist[target] == INF) {
System.out.println("目标节点不可达");
} else {
System.out.println("最短距离为: " + dist[target]);
}
Dijkstra算法是图论中最经典的最短路径算法之一，以其清晰的思路和良好的效率在实际应用中广受欢迎。本文从算法原理、实现细节到Java代码实现，全面介绍了Dijkstra算法的各个方面：
理解并掌握Dijkstra算法不仅有助于解决实际工程问题，也是学习更复杂图算法的基础。希望本文能帮助读者深入理解这一经典算法，并能在实际项目中灵活应用。