当前位置：首页 > news >正文

迪杰斯特拉算法 Dijkstra‘s Algorithm 详解

news 2025/5/16 16:29:09

迪杰斯特拉算法

迪杰斯特拉算法（Dijkstra’s Algorithm）是一个经典的图论算法，用于在带权图中寻找单源最短路径问题。该算法由荷兰计算机科学家艾兹赫尔·迪杰斯特拉于1956年提出，因其高效性和可靠性而广泛应用于网络路由、地理信息系统等领域。本文将详细介绍迪杰斯特拉算法的原理，并提供Java代码实现。

算法原理

迪杰斯特拉算法的基本思想是贪心策略，它维护两个集合：已确定最短路径的顶点集合 $S$ 和未确定最短路径的顶点集合 $U$ 。算法从起点开始，逐步将 $U$ 中的顶点按照最短路径长度加入到 $S$ 中，直到 $S$ 包含所有顶点。具体步骤如下：

初始化：设置起点 $v_0$ 的距离为0，其余顶点的距离为无穷大。将所有顶点加入 $U$ 集合。
选择：从 $U$ 中选择距离起点最小的顶点 $u$ ，将其从 $U$ 中移除并加入 $S$ 。
更新：对于 $u$ 的每个邻接点 $v$ ，如果通过 $u$ 到达 $v$ 的距离比已知的 $v$ 的距离更短，则更新 $v$ 的距离。
重复：重复步骤2和3，直到 $U$ 为空或 $S$ 包含所有顶点。

Java实现

下面是一个使用Java实现的迪杰斯特拉算法示例代码。这里使用邻接矩阵来表示图。

public class Dijkstra {public static final int MAX = Integer.MAX_VALUE; // 表示无穷大public static int[] dijkstra(int[][] graph, int start) {int n = graph.length; // 顶点数量int[] dist = new int[n]; // 存储起点到各顶点的最短距离boolean[] visited = new boolean[n]; // 标记顶点是否已访问// 初始化距离数组for (int i = 0; i < n; i++) {dist[i] = (i == start) ? 0 : MAX;}// 主循环，直到所有顶点都被访问for (int i = 0; i < n; i++) {int minDist = MAX;int u = -1; // 当前最近顶点// 选择未访问顶点中距离最小的顶点for (int j = 0; j < n; j++) {if (!visited[j] && dist[j] < minDist) {minDist = dist[j];u = j;}}if (u == -1) {break; // 所有顶点都已访问}visited[u] = true; // 标记当前顶点已访问// 更新邻接顶点的距离for (int v = 0; v < n; v++) {if (graph[u][v] != 0 && graph[u][v] + minDist < dist[v]) {dist[v] = graph[u][v] + minDist;}}}return dist; // 返回起点到各顶点的最短距离数组}public static void main(String[] args) {// 示例图int[][] graph = {{0, 4, 0, 0, 0, 0, 0, 8, 0},{4, 0, 8, 0, 0, 0, 0, 11, 0},{0, 8, 0, 7, 0, 4, 0, 0, 2},{0, 0, 7, 0, 9, 14, 0, 0, 0},{0, 0, 0, 9, 0, 10, 0, 0, 0},{0, 0, 4, 14, 10, 0, 2, 0, 0},{0, 0, 0, 0, 0, 2, 0, 1, 6},{8, 11, 0, 0, 0, 0, 1, 0, 7},{0, 0, 2, 0, 0, 0, 6, 7, 0}};int start = 0; // 起始顶点int[] distances = dijkstra(graph, start); // 计算最短距离// 输出结果for (int i = 0; i < distances.length; i++) {if (distances[i] == MAX) {System.out.println("从 " + start + " 到 " + i + " 没有路径");} else {System.out.println("从 " + start + " 到 " + i + " 的最短距离为 " + distances[i]);}}}
}