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

迪杰斯特拉算法

迪杰斯特拉算法（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]);
            }
        }
    }
}

在上面的代码中，dijkstra方法接收一个表示图的邻接矩阵和起始顶点索引，返回一个整数数组，表示从起始顶点到所有其他顶点的最短距离。MAX常量用于表示无穷大，即两个顶点之间没有直接边相连的情况。

总结

迪杰斯特拉算法是一个简单而强大的算法，用于解决单源最短路径问题。本文介绍了该算法的基本原理，并提供了一个Java实现示例。使用迪杰斯特拉算法时需要注意，该算法不适用于带负权边的图，因为在负权边存在的情况下，最短路径可能不存在或需要更复杂的算法（如贝尔曼-福德算法）来解决。

全文完！

原文地址：https://blog.csdn.net/zhuzi8849/article/details/142672359

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！