每日算法 — 使用java实现Dijkstra最短路：贪心策略与优先队列优化

Dijkstra算法是荷兰计算机科学家Edsger W. Dijkstra于1956年提出的经典单源最短路径算法。该算法采用贪心策略，通过维护一个优先队列，每次选择距离源点最近的未确定顶点进行松弛操作，逐步扩展最短路径树。本文将用Java完整实现Dijkstra算法，并讲解优先队列优化如何将时间复杂度从O(V²)降低至O((V+E)logV)。

算法核心思想

Dijkstra算法的核心在于”贪心选择”：假设源点为s，维护一个距离数组dist[]，其中dist[v]表示从s到v的当前已知最短距离。算法重复以下步骤直到所有顶点都被处理：

1. 从尚未确定的顶点中选择dist值最小的顶点u
2. 将u标记为已确定（加入最短路径树）
3. 对u的每条出边(u, v, w)，执行松弛操作：若dist[u] + w < dist[v]，则更新dist[v]

关键前提：图中所有边的权重必须为非负数。

优先队列优化原理

朴素实现使用线性扫描寻找最小dist顶点，每次O(V)，总复杂度O(V²)。使用二叉堆（PriorityQueue）优化后：

• 每次取最小值：O(logV)
• 每次松弛可能触发入堆：O(logV)
• 总复杂度：O((V + E)logV)，适合稀疏图

对于稠密图（E ≈ V²），斐波那契堆可进一步优化至O(VlogV + E)。

Java完整实现

import java.util.*;

/**
 * Dijkstra最短路算法实现
 * 使用优先队列优化，支持路径回溯
 */
public class DijkstraShortestPath {

    // 邻接表边结构
    static class Edge {
        int to;      // 目标顶点
        int weight;  // 边权重

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

    // 优先队列节点（用于堆优化）
    static class Node implements Comparable<Node> {
        int vertex;   // 顶点编号
        int dist;     // 当前距离估计值

        Node(int vertex, int dist) {
            this.vertex = vertex;
            this.dist = dist;
        }

        @Override
        public int compareTo(Node other) {
            return Integer.compare(this.dist, other.dist);
        }
    }

    /**
     * Dijkstra算法核心实现
     * @param graph 邻接表表示的图
     * @param source 源点
     * @param n 顶点数量
     * @return 距离数组
     */
    public static int[] dijkstra(List<Edge>[] graph, int source, int n) {
        // dist[i] = 源点到i的最短距离，初始为无穷大
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        // 记录每个顶点的前驱，用于路径回溯
        int[] prev = new int[n];
        Arrays.fill(prev, -1);

        // 标记顶点是否已确定最短距离
        boolean[] visited = new boolean[n];

        // 优先队列：按距离升序排列
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(source, 0));

        while (!pq.isEmpty()) {
            // 取出当前距离最小的未确定顶点
            Node curr = pq.poll();
            int u = curr.vertex;

            // 如果该顶点已处理过，跳过（处理过期条目）
            if (visited[u]) continue;
            visited[u] = true;

            // 松弛操作：遍历u的所有邻接边
            for (Edge e : graph[u]) {
                int v = e.to;
                int w = e.weight;

                // 如果找到更短路径，更新距离并入队
                if (!visited[v] && dist[u] != Integer.MAX_VALUE 
                        && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    prev[v] = u;  // 记录前驱
                    pq.offer(new Node(v, dist[v]));
                }
            }
        }

        return dist;
    }

    /**
     * 带路径回溯的Dijkstra算法
     * @return Result对象包含距离数组和前驱数组
     */
    public static Result dijkstraWithPath(List<Edge>[] graph, int source, int n) {
        int[] dist = new int[n];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[source] = 0;

        int[] prev = new int[n];
        Arrays.fill(prev, -1);

        boolean[] visited = new boolean[n];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(source, 0));

        while (!pq.isEmpty()) {
            Node curr = pq.poll();
            int u = curr.vertex;
            if (visited[u]) continue;
            visited[u] = true;

            for (Edge e : graph[u]) {
                int v = e.to, w = e.weight;
                if (!visited[v] && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    prev[v] = u;
                    pq.offer(new Node(v, dist[v]));
                }
            }
        }

        return new Result(dist, prev);
    }

    static class Result {
        int[] dist;
        int[] prev;
        Result(int[] dist, int[] prev) {
            this.dist = dist;
            this.prev = prev;
        }
    }

    /**
     * 回溯重建从source到target的最短路径
     */
    public static List<Integer> getPath(int[] prev, int source, int target) {
        List<Integer> path = new ArrayList<>();
        if (prev[target] == -1 && target != source) {
            return path; // 不可达
        }

        for (int at = target; at != -1; at = prev[at]) {
            path.add(at);
        }
        Collections.reverse(path);
        return path;
    }

    /**
     * 地图导航场景示例
     * 模拟城市间道路网络，求解最短驾车路线
     */
    public static void navigationDemo() {
        int n = 6; // 6个城市
        @SuppressWarnings("unchecked")
        List<Edge>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();

        // 城市编号: 0=北京, 1=天津, 2=济南, 3=石家庄, 4=郑州, 5=南京
        // 添加双向道路（距离单位：公里）
        addEdge(graph, 0, 1, 120);  // 北京-天津
        addEdge(graph, 0, 3, 280);  // 北京-石家庄
        addEdge(graph, 1, 2, 300);  // 天津-济南
        addEdge(graph, 2, 5, 320);  // 济南-南京
        addEdge(graph, 3, 4, 220);  // 石家庄-郑州
        addEdge(graph, 4, 5, 350);  // 郑州-南京
        addEdge(graph, 1, 3, 240);  // 天津-石家庄
        addEdge(graph, 2, 4, 180);  // 济南-郑州

        int source = 0; // 从北京出发
        Result result = dijkstraWithPath(graph, source, n);

        System.out.println("=== 城市最短距离表（从北京出发）===");
        String[] cities = {"北京", "天津", "济南", "石家庄", "郑州", "南京"};
        for (int i = 0; i < n; i++) {
            System.out.printf("到%s: %d公里\n", cities[i], 
                result.dist[i] == Integer.MAX_VALUE ? -1 : result.dist[i]);
        }

        // 输出到南京的最短路径
        int target = 5;
        List<Integer> path = getPath(result.prev, source, target);
        System.out.println("\n=== 北京到南京的最短路径 ===");
        System.out.print("路线: ");
        for (int i = 0; i < path.size(); i++) {
            System.out.print(cities[path.get(i)]);
            if (i < path.size() - 1) System.out.print(" → ");
        }
        System.out.println("\n总距离: " + result.dist[target] + "公里");
    }

    private static void addEdge(List<Edge>[] graph, int u, int v, int w) {
        graph[u].add(new Edge(v, w));
        graph[v].add(new Edge(u, w)); // 无向图
    }

    public static void main(String[] args) {
        navigationDemo();
    }
}

复杂度分析

注意：若图中存在负权边，Dijkstra算法将失效，此时应使用Bellman-Ford算法或SPFA。

实际应用扩展

1. A*算法：在Dijkstra基础上引入启发式函数h(v)，优先扩展估计总代价f(v)=g(v)+h(v)最小的节点，大幅提升目标导向搜索效率
2. 多源最短路：将所有源点同时加入优先队列，一次运行即可求得所有源点到所有点的最短距离
3. 时变网络：边权重随时间变化时，可结合时间窗口约束进行扩展