每日算法 — 使用java实现Dijkstra算法：单源最短路径与优先队列优化

在寻宝游戏的地图中，各个地点之间由不同长度的道路相连，每条道路可能有不同的通行代价（如距离、时间或风险值）。玩家需要从起点出发，以最小的总代价到达宝藏所在的位置。这个问题在图论中被称为单源最短路径问题，而Dijkstra算法正是解决此类问题的经典方法。本文将用Java实现Dijkstra算法，从基础版本到优先队列优化版本逐步深入，并探讨其在实际游戏场景中的应用。

一、问题建模：将寻宝地图抽象为带权图

我们将游戏地图抽象为一个带权有向图（Weighted Directed Graph），其中节点代表地点，边的权重代表通行代价。

1.1 核心数据结构

import java.util.*;

/**
 * 图的边：表示两个地点之间的通路及代价
 */
public class Edge {
    public final int to;      // 目标节点编号
    public final int weight;  // 边的权重（距离、时间等）

    public Edge(int to, int weight) {
        this.to = to;
        this.weight = weight;
    }

    @Override
    public String toString() {
        return String.format("Edge(to=%d, w=%d)", to, weight);
    }
}

/**
 * 带权有向图，使用邻接表存储
 * 适合稀疏图，空间复杂度 O(V + E)
 */
public class WeightedGraph {
    private final int vertexCount;           // 顶点数
    private final List<List<Edge>> adjList;  // 邻接表

    public WeightedGraph(int vertexCount) {
        this.vertexCount = vertexCount;
        this.adjList = new ArrayList<>(vertexCount);
        for (int i = 0; i < vertexCount; i++) {
            adjList.add(new ArrayList<>());
        }
    }

    /**
     * 添加有向边
     * @param from   起点
     * @param to     终点
     * @param weight 权重
     */
    public void addEdge(int from, int to, int weight) {
        adjList.get(from).add(new Edge(to, weight));
    }

    /**
     * 添加无向边（双向添加）
     */
    public void addUndirectedEdge(int u, int v, int weight) {
        addEdge(u, v, weight);
        addEdge(v, u, weight);
    }

    public List<Edge> getNeighbors(int vertex) {
        return adjList.get(vertex);
    }

    public int getVertexCount() {
        return vertexCount;
    }
}

1.2 寻宝地图示例

/**
 * 构建一个示例寻宝地图
 * 节点0: 起点村庄
 * 节点1: 森林入口
 * 节点2: 河流渡口
 * 节点3: 古老神庙
 * 节点4: 龙之巢穴（宝藏所在地）
 * 节点5: 隐秘捷径
 */
public static WeightedGraph createTreasureMap() {
    WeightedGraph graph = new WeightedGraph(6);
    // 起点到各区域
    graph.addUndirectedEdge(0, 1, 4);  // 村庄 -> 森林 (距离4)
    graph.addUndirectedEdge(0, 2, 2);  // 村庄 -> 河流 (距离2)
    graph.addUndirectedEdge(1, 2, 1);  // 森林 -> 河流 (距离1)
    graph.addUndirectedEdge(1, 3, 5);  // 森林 -> 神庙 (距离5)
    graph.addUndirectedEdge(2, 3, 8);  // 河流 -> 神庙 (距离8)
    graph.addUndirectedEdge(2, 4, 10); // 河流 -> 龙巢 (距离10)
    graph.addUndirectedEdge(3, 4, 2);  // 神庙 -> 龙巢 (距离2)
    graph.addUndirectedEdge(3, 5, 3);  // 神庙 -> 捷径 (距离3)
    graph.addUndirectedEdge(2, 5, 6);  // 河流 -> 捷径 (距离6)
    graph.addUndirectedEdge(4, 5, 7);  // 龙巢 -> 捷径 (距离7)
    return graph;
}

二、Dijkstra算法原理：贪心策略与松弛操作

Dijkstra算法的核心思想是贪心策略：每次从未确定最短路径的节点中，选择距离起点最近的一个，然后利用它去”松弛”（更新）其邻接节点的距离估计值。

2.1 算法步骤

1. 初始化：起点距离设为0，其余所有节点距离设为无穷大。
2. 选择最小距离节点：在未访问节点中，选择距离起点最近的节点 u。
3. 标记访问：将 u 标记为已确定最短路径。
4. 松弛操作：遍历 u 的所有邻接节点 v，如果 dist[u] + weight(u,v) < dist[v]，则更新 dist[v]。
5. 重复步骤2-4，直到所有节点都被访问或目标节点被确定。

2.2 为什么Dijkstra算法有效

Dijkstra算法成立的前提是所有边的权重非负。由于每次选择的都是当前距离最小的未确定节点，且边权非负，不存在通过其他未确定节点使该节点距离更小的可能。这保证了贪心选择的正确性。

三、基础实现：数组版Dijkstra

使用数组维护距离和访问状态，时间复杂度为 O(V²)，适合稠密图或节点数较少的场景。

import java.util.*;

/**
 * 基础版Dijkstra算法（数组实现）
 * 时间复杂度: O(V²)
 * 空间复杂度: O(V)
 */
public class DijkstraArray {

    /**
     * 计算从起点source到所有节点的最短距离
     * @return dist数组，dist[i]表示source到i的最短距离
     */
    public static int[] shortestPath(WeightedGraph graph, int source) {
        int n = graph.getVertexCount();
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];  // 记录前驱节点，用于重建路径

        // 初始化：距离设为无穷大（用Integer.MAX_VALUE / 2避免溢出）
        Arrays.fill(dist, Integer.MAX_VALUE / 2);
        Arrays.fill(parent, -1);
        dist[source] = 0;

        // 进行n轮迭代，每轮确定一个节点的最短距离
        for (int i = 0; i < n; i++) {
            // 步骤1：在未访问节点中选择距离最小的
            int u = -1;
            int minDist = Integer.MAX_VALUE / 2;
            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;

            // 步骤2：松弛u的所有邻接节点
            for (Edge edge : graph.getNeighbors(u)) {
                int v = edge.to;
                int weight = edge.weight;
                if (!visited[v] && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                    parent[v] = u;  // 记录v的前驱是u
                }
            }
        }

        return dist;
    }

    /**
     * 计算最短路径，同时返回前驱数组用于路径重建
     */
    public static Result compute(WeightedGraph graph, int source) {
        int n = graph.getVertexCount();
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];

        Arrays.fill(dist, Integer.MAX_VALUE / 2);
        Arrays.fill(parent, -1);
        dist[source] = 0;

        for (int i = 0; i < n; i++) {
            int u = -1;
            int minDist = Integer.MAX_VALUE / 2;
            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 (Edge edge : graph.getNeighbors(u)) {
                int v = edge.to;
                if (!visited[v] && dist[u] + edge.weight < dist[v]) {
                    dist[v] = dist[u] + edge.weight;
                    parent[v] = u;
                }
            }
        }

        return new Result(dist, parent);
    }

    public record Result(int[] dist, int[] parent) {}

    /**
     * 根据前驱数组重建从source到target的最短路径
     */
    public static List<Integer> reconstructPath(int[] parent, int source, int target) {
        LinkedList<Integer> path = new LinkedList<>();
        int cur = target;
        while (cur != -1) {
            path.addFirst(cur);
            if (cur == source) break;
            cur = parent[cur];
        }
        // 如果起点无法到达终点
        if (path.getFirst() != source) {
            return Collections.emptyList();
        }
        return path;
    }
}

3.1 基础版测试

public class Main {
    public static void main(String[] args) {
        WeightedGraph graph = createTreasureMap();
        int source = 0;  // 起点：村庄
        int target = 4;  // 终点：龙巢

        DijkstraArray.Result result = DijkstraArray.compute(graph, source);
        int[] dist = result.dist();
        int[] parent = result.parent();

        System.out.println("=== 基础版Dijkstra结果 ===");
        System.out.println("从村庄(0)到各点的最短距离:");
        String[] names = {"村庄", "森林", "河流", "神庙", "龙巢", "捷径"};
        for (int i = 0; i < dist.length; i++) {
            System.out.printf("  到%s(%d): %d%n", names[i], i,
                dist[i] == Integer.MAX_VALUE / 2 ? -1 : dist[i]);
        }

        List<Integer> path = DijkstraArray.reconstructPath(parent, source, target);
        System.out.println("\n最短路径: " + path);
        System.out.println("路径详情: " + path.stream()
            .map(i -> names[i] + "(" + i + ")")
            .reduce((a, b) -> a + " -> " + b).orElse(""));
        System.out.println("总代价: " + dist[target]);
    }
}

输出结果：

从村庄(0)到各点的最短距离:
  到村庄(0): 0
  到森林(1): 3
  到河流(2): 2
  到神庙(3): 8
  到龙巢(4): 10
  到捷径(5): 11

最短路径: [0, 2, 1, 3, 4]
路径详情: 村庄(0) -> 河流(2) -> 森林(1) -> 神庙(3) -> 龙巢(4)
总代价: 10

四、优先队列优化：堆实现Dijkstra

基础版每次都要线性扫描所有未访问节点来找出最小值，效率较低。当使用优先队列（最小堆）维护未确定节点时，可以将时间复杂度优化至 O(E log V)，这在稀疏图中是巨大的提升。

import java.util.*;

/**
 * 优先队列优化版Dijkstra算法
 * 时间复杂度: O(E log V)
 * 空间复杂度: O(V)
 */
public class DijkstraHeap {

    /**
     * 优先队列中的节点，按当前距离排序
     */
    private record PQNode(int vertex, int dist) implements Comparable<PQNode> {
        @Override
        public int compareTo(PQNode other) {
            return Integer.compare(this.dist, other.dist);
        }
    }

    public static DijkstraArray.Result compute(WeightedGraph graph, int source) {
        int n = graph.getVertexCount();
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];

        Arrays.fill(dist, Integer.MAX_VALUE / 2);
        Arrays.fill(parent, -1);
        dist[source] = 0;

        // 最小堆，按距离排序
        PriorityQueue<PQNode> pq = new PriorityQueue<>();
        pq.offer(new PQNode(source, 0));

        while (!pq.isEmpty()) {
            PQNode current = pq.poll();
            int u = current.vertex;

            // 如果该节点已经被处理过，跳过（处理过期条目）
            if (visited[u]) continue;
            // 如果堆中距离已经大于当前已知最短距离，跳过
            if (current.dist > dist[u]) continue;

            visited[u] = true;

            // 松弛邻接节点
            for (Edge edge : graph.getNeighbors(u)) {
                int v = edge.to;
                int newDist = dist[u] + edge.weight;
                if (!visited[v] && newDist < dist[v]) {
                    dist[v] = newDist;
                    parent[v] = u;
                    pq.offer(new PQNode(v, newDist));
                }
            }
        }

        return new DijkstraArray.Result(dist, parent);
    }

    /**
     * 优化版：只计算到目标节点的最短路径，提前终止
     * 当只需要单目标最短路径时，目标确定后即可结束
     */
    public static DijkstraArray.Result computeToTarget(
            WeightedGraph graph, int source, int target) {
        int n = graph.getVertexCount();
        int[] dist = new int[n];
        boolean[] visited = new boolean[n];
        int[] parent = new int[n];

        Arrays.fill(dist, Integer.MAX_VALUE / 2);
        Arrays.fill(parent, -1);
        dist[source] = 0;

        PriorityQueue<PQNode> pq = new PriorityQueue<>();
        pq.offer(new PQNode(source, 0));

        while (!pq.isEmpty()) {
            PQNode current = pq.poll();
            int u = current.vertex;

            if (visited[u]) continue;
            if (current.dist > dist[u]) continue;

            visited[u] = true;

            // 提前终止：目标节点已确定最短距离
            if (u == target) {
                break;
            }

            for (Edge edge : graph.getNeighbors(u)) {
                int v = edge.to;
                int newDist = dist[u] + edge.weight;
                if (!visited[v] && newDist < dist[v]) {
                    dist[v] = newDist;
                    parent[v] = u;
                    pq.offer(new PQNode(v, newDist));
                }
            }
        }

        return new DijkstraArray.Result(dist, parent);
    }
}

五、复杂度对比与适用场景

在寻宝游戏中，地图通常是稀疏图（每个地点只与少数相邻地点连通），因此优先队列版本是最佳选择。

六、游戏扩展：带障碍的动态地图

实际游戏中，地图可能动态变化（如桥梁被摧毁、新道路开通）。Dijkstra算法可以配合增量更新或定期重新计算来适应动态环境。

/**
 * 动态路径规划器：支持边权变更后快速重新计算
 */
public class DynamicPathPlanner {
    private final WeightedGraph graph;
    private int[] currentDist;
    private int[] currentParent;
    private final int source;

    public DynamicPathPlanner(WeightedGraph graph, int source) {
        this.graph = graph;
        this.source = source;
        recompute();
    }

    /**
     * 重新计算最短路径
     */
    public void recompute() {
        DijkstraArray.Result result = DijkstraHeap.compute(graph, source);
        this.currentDist = result.dist();
        this.currentParent = result.parent();
    }

    /**
     * 获取到目标点的当前最短路径
     */
    public List<Integer> getPathTo(int target) {
        return DijkstraArray.reconstructPath(currentParent, source, target);
    }

    /**
     * 获取到目标点的当前距离
     */
    public int getDistanceTo(int target) {
        return currentDist[target];
    }

    /**
     * 模拟地图变化：某条道路通行代价改变
     */
    public void onEdgeChanged(int from, int to, int newWeight) {
        // 简化的处理：直接重新计算
        // 更高效的方案可以使用动态Dijkstra或A*增量算法
        System.out.printf("地图更新: %d -> %d 的权重变为 %d%n", from, to, newWeight);
        recompute();
    }
}

七、总结

本文从寻宝游戏场景出发，完整讲解了Dijkstra算法的原理与Java实现：

• 数组版（O(V²)）适合小规模稠密图，代码直观易于理解。
• 优先队列版（O(E log V)）是稀疏图的标准选择，配合提前终止可进一步优化单目标查询。
• 通过前驱数组可以方便地重建完整的最短路径，而非仅得到距离值。
• 算法成立的前提是边权非负，若存在负权边需要使用Bellman-Ford算法。

Dijkstra算法不仅是图论的基石，也是游戏开发中NPC寻路、网络路由、物流规划等领域的核心工具。掌握它的实现细节，对理解更复杂的A*算法（在Dijkstra基础上加入启发函数）也大有裨益。