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

聊到 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[u] 设为 true，表示这个点的最短距离已经定下来了。
• 松弛：遍历 u 的所有邻接点 v，如果 dist[u] + weight < dist[v]，就更新 dist[v]。

注意细节：如果你用的是邻接矩阵 graph[u][v]，权值非负，用 0 或 Integer.MAX_VALUE 表示没有边；要是邻接表，就得额外遍历每个顶点的邻居列表。

关键细节与常见陷阱

用数组实现时，有几个容易翻车的地方值得多看一眼：

• 别让整数溢出坑了你：比较 dist[u] + weight < dist[v] 之前，一定先判断 dist[u] == Integer.MAX_VALUE。不然加出来的负数会让你一脸懵，直接导致错误更新。
• 负权边？想都别想：Dijkstra 天生不认负权边，数组实现也救不了，换个算法吧。
• 不可达就是不可达：最终 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 < n; i++) {
    // 找当前未访问的最小距离顶点
    int u = -1;
    for (int j = 0; j < n; j++) {
        if (!visited[j] && (u == -1 || dist[j] < dist[u])) u = j;
    }
    if (u == -1 || dist[u] == INF) break; // 剩余不可达，提前退出
    visited[u] = true;

    // 松弛所有邻接点
    for (int v = 0; v < n; v++) {
        if (graph[u][v] != INF && dist[u] != INF) { // 防溢出
            int alt = dist[u] + graph[u][v];
            if (alt < dist[v]) dist[v] = alt;
        }
    }
}

这个实现的时间复杂度是 O(V²)，适合 V ≤ 1000 的稠密图。如果顶点多且图稀疏，建议改用堆优化版本（PriorityQueue），性能会好不少。