Dijkstra 算法简介
Dijkstra 算法是用于寻找图中从单一源点到所有其他顶点的最短路径的经典算法，它适用于非负权重的图。
（图片来源网络，侵删）
核心思想：
- 贪心策略：算法从源点开始，逐步向外扩展，在每一步，都选择当前距离源点最近的、尚未被访问的顶点，并更新其所有邻居顶点的最短路径估计。
- 松弛操作：这是算法的核心步骤，对于顶点
u的每一个邻居v，检查从源点经过u到达v的路径是否比当前已知的到达v的路径更短，如果是，则更新v的最短路径距离和前驱节点。 - 数据结构：为了高效地找到当前距离源点最近的顶点，通常使用优先队列（最小堆）来实现。
Java 实现
我们将使用邻接表来表示图,并使用 Java 的 PriorityQueue 作为优先队列。
1 数据结构定义
我们需要定义图的节点和边。
Edge.java - 表示图中的边
（图片来源网络，侵删）
public class Edge {
private int targetNode; // 目标节点
private int weight; // 边的权重
public Edge(int targetNode, int weight) {
this.targetNode = targetNode;
this.weight = weight;
}
public int getTargetNode() {
return targetNode;
}
public int getWeight() {
return weight;
}
}
Node.java - 优先队列中的节点包装类
为了在 PriorityQueue 中能够根据距离进行排序，我们需要一个包装类。
import java.util.Comparator;
public class Node implements Comparator<Node> {
public int node; // 顶点的标识
public int cost; // 从源点到该顶点的当前最短距离
public Node() {}
public Node(int node, int cost) {
this.node = node;
this.cost = cost;
}
@Override
public int compare(Node node1, Node node2) {
// 用于优先队列，使 cost 小的节点排在前面
return Integer.compare(node1.cost, node2.cost);
}
}
2 Dijkstra 算法核心实现
DijkstraAlgorithm.java
import java.util.*;
public class DijkstraAlgorithm {
// 主方法：计算从源点到所有其他顶点的最短路径
public void computePaths(int source, List<List<Edge>> adjacencyList, int numVertices) {
// 1. 初始化距离数组和前驱数组
int[] distances = new int[numVertices];
int[] predecessors = new int[numVertices];
Arrays.fill(distances, Integer.MAX_VALUE); // 初始距离设为无穷大
Arrays.fill(predecessors, -1); // 前驱节点初始为-1（表示无前驱）
distances[source] = 0; // 源点到自身的距离为0
// 2. 创建优先队列，并加入源点
// 使用我们自定义的 Node 类，并实现 Comparator
PriorityQueue<Node> pq = new PriorityQueue<>(numVertices, new Node());
pq.add(new Node(source, 0));
// 3. 主循环
while (!pq.isEmpty()) {
// a. 取出当前距离源点最近的节点 u
Node currentNode = pq.poll();
int u = currentNode.node;
// b. 如果当前计算出的距离比优先队列中的距离大，说明是过时信息，跳过
// 这是一个重要的优化，可以避免处理无效的节点
if (currentNode.cost > distances[u]) {
continue;
}
// c. 遍历 u 的所有邻居 v
for (Edge edge : adjacencyList.get(u)) {
int v = edge.getTargetNode();
int weight = edge.getWeight();
int distanceThroughU = distances[u] + weight;
// d. 松弛操作
if (distanceThroughU < distances[v]) {
// 找到了更短的路径
distances[v] = distanceThroughU;
predecessors[v] = u;
// 将更新后的节点 v 加入优先队列
pq.add(new Node(v, distances[v]));
}
}
}
// 4. 打印结果
printSolution(source, distances, predecessors);
}
// 打印最终的最短路径结果
private void printSolution(int source, int[] distances, int[] predecessors) {
System.out.println("Dijkstra Algorithm Results:");
System.out.println("Source Node: " + source);
System.out.println("Node\tDistance from Source\tPath");
System.out.println("----------------------------------------");
for (int i = 0; i < distances.length; i++) {
if (i == source) continue; // 源点到自身的路径可以省略或特殊处理
if (distances[i] == Integer.MAX_VALUE) {
System.out.println(i + "\t\t" + "Infinity" + "\t\t" + "No path");
} else {
System.out.print(i + "\t\t" + distances[i] + "\t\t\t");
printPath(i, predecessors);
System.out.println();
}
}
}
// 递归打印从源点到目标节点的路径
private void printPath(int target, int[] predecessors) {
if (predecessors[target] == -1) {
System.out.print(target);
return;
}
printPath(predecessors[target], predecessors);
System.out.print(" -> " + target);
}
}
3 完整示例与主方法
让我们创建一个 Main 类来运行这个算法。
Main.java
（图片来源网络，侵删）
import java.util.ArrayList;
import java.util.List;
public class Main {
public static void main(String[] args) {
// 1. 创建图
int numVertices = 6;
List<List<Edge>> adjacencyList = new ArrayList<>(numVertices);
for (int i = 0; i < numVertices; i++) {
adjacencyList.add(new ArrayList<>());
}
// 添加边 (无向图，所以添加两个方向的边)
// 图结构如下:
// 0 -- 1 -- 2 -- 5
// | / | |
// 3 -- 4 -- 5
adjacencyList.get(0).add(new Edge(1, 7));
adjacencyList.get(0).add(new Edge(3, 9));
adjacencyList.get(0).add(new Edge(4, 14));
adjacencyList.get(1).add(new Edge(0, 7));
adjacencyList.get(1).add(new Edge(2, 10));
adjacencyList.get(1).add(new Edge(3, 15));
adjacencyList.get(1).add(new Edge(4, 10));
adjacencyList.get(2).add(new Edge(1, 10));
adjacencyList.get(2).add(new Edge(3, 11));
adjacencyList.get(2).add(new Edge(5, 2));
adjacencyList.get(3).add(new Edge(0, 9));
adjacencyList.get(3).add(new Edge(1, 15));
adjacencyList.get(3).add(new Edge(2, 11));
adjacencyList.get(3).add(new Edge(4, 6));
adjacencyList.get(4).add(new Edge(0, 14));
adjacencyList.get(4).add(new Edge(1, 10));
adjacencyList.get(4).add(new Edge(3, 6));
adjacencyList.get(4).add(new Edge(5, 9));
adjacencyList.get(5).add(new Edge(2, 2));
adjacencyList.get(5).add(new Edge(4, 9));
// 2. 运行 Dijkstra 算法
DijkstraAlgorithm dijkstra = new DijkstraAlgorithm();
dijkstra.computePaths(0, adjacencyList, numVertices);
}
}
4 运行结果
运行 Main.java，你将得到以下输出：
Dijkstra Algorithm Results:
Source Node: 0
Node Distance from Source Path
----------------------------------------
1 7 0 -> 1
2 17 0 -> 1 -> 2
3 20 0 -> 1 -> 3
4 14 0 -> 4
5 19 0 -> 1 -> 2 -> 5结果解读：
- 从源点
0到节点1的最短距离是7，路径是0 -> 1。 - 从源点
0到节点5的最短距离是19，路径是0 -> 1 -> 2 -> 5。
算法复杂度分析
Dijkstra 算法的性能很大程度上取决于优先队列的实现。
-
时间复杂度：
- 使用数组作为优先队列：每次从
V个顶点中找到最小距离的顶点需要O(V)时间，每个顶点会出队一次，每个顶点的所有边都会被检查一次，总复杂度为O(V^2 + E)，对于稠密图（E接近V^2），这是一个不错的选择。 - 使用二叉堆（
java.util.PriorityQueue）：插入和删除最小元素的操作复杂度为O(log V)，每个顶点最多插入和删除一次，每条边都会触发一次插入或更新操作，最坏情况下，总复杂度为O((V + E) log V)，对于稀疏图（E远小于V^2），这更高效。 - 使用斐波那契堆：理论上，斐波那契堆可以将插入和减小关键值的操作优化到
O(1)均摊时间，删除最小元素为O(log V)，这使得总复杂度降低到O(E + V log V)，但在实际应用中，由于其常数因子较大，Java 的PriorityQueue（二叉堆）通常是更实际和高效的选择。
- 使用数组作为优先队列：每次从
-
空间复杂度：
O(V + E)：用于存储邻接表。O(V)：用于存储距离数组和前驱数组。O(V)：优先队列在最坏情况下可能包含所有顶点。- 总空间复杂度为
O(V + E)。
重要注意事项
- 非负权重：Dijkstra 算法要求数字所有边的权重都必须是非负数，如果图中存在负权边，算法可能会失败，因为它会错误地认为已经找到了最短路径，从而不再检查可能更短的路径，对于含负权边的图，应使用 Bellman-Ford 算法。
- 单源最短路径：该算法专门解决从一个源点到所有其他点的最短路径问题，如果想求任意两点间的最短路径，可以运行
V次 Dijkstra 算法（每次以一个不同的顶点为源点），或者使用 Floyd-Warshall 算法。 - 图的表示：邻接表是表示稀疏图（边数远小于顶点数的平方）的高效方式，对于稠密图，邻接矩阵可能更合适。
