如何在 Java 中利用数组实现简单的迪杰斯特拉（Dijkstra）算法中的距离状态表-java教程-PHP中文网

dijkstra算法用数组实现时，核心是dist[]记录源点到各顶点当前最短距离，visited[]标记是否已确定最短路径；初始化dist[src]=0、其余为integer.max_value，visited全为false；每轮选未访问中dist最小顶点u，标记visited[u]=true，并用u松弛所有邻接点v：若dist[u]+weight

如何在 java 中利用数组实现简单的迪杰斯特拉（dijkstra）算法中的距离状态表

在 Java 中用数组实现 Dijkstra 算法的距离状态表，核心是用一个一维数组 dist[] 记录从源点到各顶点的当前最短距离，并配合一个布尔数组 visited[] 标记顶点是否已确定最短路径。这种方式适合顶点数不多、图结构较简单（如邻接矩阵存储）的场景，代码简洁、易理解。

距离数组与访问标记数组的定义

假设图有 n 个顶点（编号 0 到 n−1），源点为 src：

int[] dist = new int[n];：初始时除 dist[src] = 0 外，其余设为 Integer.MAX_VALUE（表示不可达）
boolean[] visited = new boolean[n];：记录每个顶点是否已找到最终最短距离

初始化与主循环逻辑

初始化后，进行 n 轮迭代，每轮选出未访问中 dist 最小的顶点 u，并用它松弛其所有邻接点：

查找最小未访问顶点：遍历 visited[i] == false 的所有 i，取 dist[i] 最小者（可用简单线性扫描，无需优先队列）
标记 visited[u] = true
对每个邻接顶点 v（即图中存在边 u → v，权值为 weight），若 dist[u] + weight ，则更新 <code>dist[v] = dist[u] + weight

注意：若用邻接矩阵 graph[u][v] 存储，权值为非负整数，0 或 Integer.MAX_VALUE 表示无边；若用邻接表，需额外遍历每个顶点的邻接链表。

Java Maven Secondary Analysis

分析ZIP压缩包或GitLab仓库中的Java Maven项目，确定二次开发范围、类数量、模块分布及生产相关指标。

下载

关键细节与常见陷阱

使用数组实现时需特别注意：

避免整数溢出：比较 dist[u] + weight 前，先判断 <code>dist[u] == Integer.MAX_VALUE，否则加法可能溢出变负数，导致错误更新
权值必须非负：Dijkstra 不适用于含负权边的图，否则数组方式也无法挽救算法失效
不可达顶点保持 MAX_VALUE：最终 dist[i] == Integer.MAX_VALUE 即表示从源点无法到达顶点 i

简化的代码片段示意

以邻接矩阵为例（无边用 INF = Integer.MAX_VALUE 表示）：

final int INF = Integer.MAX_VALUE;
int n = graph.length;
int[] dist = new int[n];
boolean[] visited = new boolean[n];
Arrays.fill(dist, INF);
dist[src] = 0;

for (int i = 0; i

该实现时间复杂度为 O(V²)，适合 V ≤ 1000 的稠密图；若顶点多且稀疏，建议改用堆优化（PriorityQueue）。