在计算机科学中，图论是一个非常重要的研究领域，而最短路径问题则是其中的核心内容之一。迪杰斯特拉（Dijkstra）算法是解决单源最短路径问题的经典方法，广泛应用于网络路由、地图导航等多个实际场景中。本文将详细介绍如何使用 Java 语言实现该算法，并提供完整的代码示例。
迪杰斯特拉算法简介
迪杰斯特拉算法由荷兰计算机科学家艾兹赫尔·迪杰斯特拉（Edsger W. Dijkstra）于1956年提出，用于计算图中从一个起点到其他所有节点的最短路径。该算法适用于边权为非负数的图结构。
其基本思想是：维护一个已确定最短路径的顶点集合，每次从未确定的顶点中选择距离最小的节点进行扩展，逐步更新其他顶点的最短路径估计值。
算法步骤
1. 初始化距离数组，将起点的距离设为0，其余设为无穷大。
2. 创建一个未访问顶点集合。
3. 从起点开始，依次选取当前距离最小的顶点，将其加入已访问集合。
4. 对该顶点的所有邻接顶点进行松弛操作，即检查是否可以通过当前顶点找到更短的路径。
5. 重复上述步骤，直到所有顶点都被访问或目标顶点被处理。
Java 实现代码
以下是一个使用 Java 实现的迪杰斯特拉算法示例：
```java
import java.util.;
public class DijkstraAlgorithm {
static class Edge {
int to;
int weight;
public Edge(int to, int weight) {
this.to = to;
this.weight = weight;
}
}
public static void dijkstra(List
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[start] = 0;
boolean[] visited = new boolean[n];
PriorityQueue
pq.offer(new int[]{start, 0});
while (!pq.isEmpty()) {
int[] current = pq.poll();
int u = current[0];
int d = current[1];
if (visited[u]) continue;
visited[u] = true;
for (Edge edge : graph.get(u)) {
int v = edge.to;
int w = edge.weight;
if (dist[v] > d + w) {
dist[v] = d + w;
pq.offer(new int[]{v, dist[v]});
}
}
}
// 输出结果
System.out.println("从起点 " + start + " 到各节点的最短距离：");
for (int i = 0; i < n; i++) {
System.out.println("节点 " + i + " 的最短距离: " + dist[i]);
}
}
public static void main(String[] args) {
int n = 5; // 节点数量
List
for (int i = 0; i < n; i++) {
graph.add(new ArrayList<>());
}
// 添加边
graph.get(0).add(new Edge(1, 10));
graph.get(0).add(new Edge(4, 5));
graph.get(1).add(new Edge(2, 1));
graph.get(1).add(new Edge(3, 2));
graph.get(2).add(new Edge(3, 4));
graph.get(3).add(new Edge(4, 3));
graph.get(4).add(new Edge(1, 2));
dijkstra(graph, 0, n);
}
}
```
代码说明
- `Edge` 类用于表示图中的边，包含目标节点和权重。
- `dijkstra` 方法接收图结构、起始节点和节点总数作为参数。
- 使用优先队列（`PriorityQueue`）来高效地获取当前距离最小的节点。
- 最后输出每个节点到起点的最短路径长度。
总结
通过以上代码，我们可以看到 Java 如何实现迪杰斯特拉算法，理解其核心逻辑并灵活运用于实际项目中。对于学习图论和算法的人来说，这是一个非常实用的入门示例。希望本文能帮助你更好地掌握这一经典算法。
