Java图最短路径算法实现技巧

Dijkstra算法适用于无负权边的单源最短路径问题，通过优先队列优化实现O(E log V)时间复杂度，使用邻接表存储稀疏图更高效；若存在负权边则需采用Bellman-Ford算法，其能检测负环但时间复杂度为O(V*E)；而Floyd-Warshall算法用于多源最短路径，基于动态规划思想，时间复杂度O(V^3)，适合节点数较少的图。

Java实现图的最短路径算法，主要有两种经典方法：Dijkstra算法（单源）和Floyd-Warshall算法（多源）。选择哪个取决于你的具体需求：是想知道从一个点到所有点的最短路径，还是所有点到所有点的最短路径。另外，如果图中有负权边，Dijkstra就失效了，这时候需要考虑Bellman-Ford算法。

解决方案

实现最短路径算法，我通常会从图的表示开始。最常见的无非是邻接矩阵和邻接表，我个人偏爱邻接表，尤其对于稀疏图来说，它在空间和时间上都更有效率。

以Dijkstra算法为例，这是我处理单源最短路径问题时最常用的工具。它的核心思想是贪婪地选择当前已知最短路径的未访问节点。

import java.util.*;

public class DijkstraShortestPath {

    // 定义一个内部类来表示图中的边，包含目标节点和权重
    static class Edge {
        int to;
        int weight;

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

    // Dijkstra算法实现
    public int[] dijkstra(List> adj, int startNode, int numNodes) {
        // dist[i] 存储从startNode到节点i的最短距离
        int[] dist = new int[numNodes];
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化所有距离为无穷大
        dist[startNode] = 0; // 起始节点到自身的距离为0

        // 优先队列，存储Pair<距离, 节点>，按距离升序排列
        // 这样每次都能取出距离起始点最近的未访问节点
        PriorityQueue> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.getKey()));

        pq.offer(new Pair<>(0, startNode)); // 将起始节点加入队列

        // 记录节点是否已被访问（即其最短路径是否已确定）
        boolean[] visited = new boolean[numNodes];

        while (!pq.isEmpty()) {
            Pair current = pq.poll();
            int u = current.getValue(); // 当前访问的节点
            int d = current.getKey(); // 当前节点到起始点的距离

            if (visited[u]) {
                continue; // 如果已访问过，跳过
            }
            visited[u] = true; // 标记为已访问

            // 遍历当前节点u的所有邻居
            for (Edge edge : adj.get(u)) {
                int v = edge.to;
                int weight = edge.weight;

                // 如果通过当前节点u到达v的路径更短
                if (dist[u] != Integer.MAX_VALUE && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight; // 更新最短距离
                    pq.offer(new Pair<>(dist[v], v)); // 将v加入优先队列
                }
            }
        }
        return dist;
    }

    // 辅助类：简单的Pair，因为Java标准库没有内置的Pair
    static class Pair {
        private final K key;
        private final V value;

        public Pair(K key, V value) {
            this.key = key;
            this.value = value;
        }

        public K getKey() { return key; }
        public V getValue() { return value; }
    }

    // 示例用法
    public static void main(String[] args) {
        int numNodes = 5; // 0-4号节点
        List> adj = new ArrayList<>();
        for (int i = 0; i < numNodes; i++) {
            adj.add(new ArrayList<>());
        }

        // 添加边：(from, to, weight)
        adj.get(0).add(new Edge(1, 10));
        adj.get(0).add(new Edge(4, 5));
        adj.get(1).add(new Edge(2, 1));
        adj.get(1).add(new Edge(4, 2));
        adj.get(2).add(new Edge(3, 4));
        adj.get(3).add(new Edge(2, 6));
        adj.get(4).add(new Edge(1, 3));
        adj.get(4).add(new Edge(2, 9));
        adj.get(4).add(new Edge(3, 2));

        DijkstraShortestPath solver = new DijkstraShortestPath();
        int startNode = 0;
        int[] shortestDistances = solver.dijkstra(adj, startNode, numNodes);

        System.out.println("从节点 " + startNode + " 到其他节点的最短距离:");
        for (int i = 0; i < numNodes; i++) {
            if (shortestDistances[i] == Integer.MAX_VALUE) {
                System.out.println("到节点 " + i + ": 无法到达");
            } else {
                System.out.println("到节点 " + i + ": " + shortestDistances[i]);
            }
        }
        // 预期输出：
        // 到节点 0: 0
        // 到节点 1: 8 (0->4->1)
        // 到节点 2: 9 (0->4->1->2)
        // 到节点 3: 7 (0->4->3)
        // 到节点 4: 5 (0->4)
    }
}

单源最短路径：Dijkstra算法的Java实现细节与优化

Dijkstra算法是解决单源最短路径问题的不二之选，前提是图中没有负权边。它的核心在于一个贪婪策略：每次从“待处理”的节点中，选择当前距离起始点最近的那个。

在Java中实现Dijkstra，最关键的是数据结构的选择。我通常会用List>来表示图的邻接表，其中Edge是一个自定义的类，包含目标节点和边的权重。这个选择在处理稀疏图时尤其高效，因为它只存储实际存在的边，不像邻接矩阵那样需要为所有可能的边分配空间。

另一个核心是java.util.PriorityQueue。这个优先队列是Dijkstra算法性能的关键。它能保证我们每次取出的都是当前距离起始点最近的未访问节点。队列里通常存的是一个Pair，第一个Integer是当前节点到源点的距离，第二个是节点本身的ID。Java的PriorityQueue默认是最小堆，这正好符合我们的需求。

踩坑点：

• 负权边： 别忘了Dijkstra对负权边是无能为力的。如果图里有负权边，它可能会给出错误的答案。这时候，我就会转向Bellman-Ford算法。
• Integer.MAX_VALUE溢出： 在计算dist[u] + weight时，如果dist[u]已经是Integer.MAX_VALUE，再加上一个正数可能会导致溢出变成负数，从而出现意想不到的“最短路径”。所以，在判断dist[u] != Integer.MAX_VALUE时要小心。
• 重复入队： 优先队列可能会把同一个节点以不同的路径和距离多次入队。这是正常的，因为我们只关心第一次以最短路径到达该节点时的处理。通过visited数组可以有效避免重复处理已确定最短路径的节点。

至于优化，使用PriorityQueue本身就是一种优化，它将查找最近节点的复杂度从O(V)降到了O(log V)。对于非常大的图，理论上可以使用斐波那契堆（Fibonacci Heap）进一步优化，但那玩意儿实现起来复杂，而且在实际工程中，Java内置的PriorityQueue（基于二叉堆）通常已经足够了。

处理负权边：Bellman-Ford算法的Java实现与负环检测

当图中有负权边时，Dijkstra算法就派不上用场了。这时，Bellman-Ford算法就成了我的首选。它虽然比Dijkstra慢，但胜在能处理负权边，并且还能检测出负环。负环是个麻烦事儿，因为它意味着某些路径可以无限缩短，导致最短路径没有定义。

Bellman-Ford算法的核心思想是进行V-1次迭代（V是节点数量）。在每次迭代中，它会尝试放松图中的所有边。所谓“放松”，就是检查通过这条边是否能找到一条更短的路径。

import java.util.Arrays;
import java.util.List;
import java.util.ArrayList;

public class BellmanFordShortestPath {

    static class Edge {
        int from;
        int to;
        int weight;

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

    public int[] bellmanFord(List edges, int numNodes, int startNode) {
        int[] dist = new int[numNodes];
        Arrays.fill(dist, Integer.MAX_VALUE);
        dist[startNode] = 0;

        // 进行 V-1 次迭代
        for (int i = 0; i < numNodes - 1; i++) {
            for (Edge edge : edges) {
                // 只有当起点可达时才尝试放松
                if (dist[edge.from] != Integer.MAX_VALUE && dist[edge.from] + edge.weight < dist[edge.to]) {
                    dist[edge.to] = dist[edge.from] + edge.weight;
                }
            }
        }

        // 第 V 次迭代用于检测负环
        for (Edge edge : edges) {
            if (dist[edge.from] != Integer.MAX_VALUE && dist[edge.from] + edge.weight < dist[edge.to]) {
                // 如果在第 V 次迭代中还能放松成功，说明存在负环
                System.out.println("图中存在负环！最短路径无法确定。");
                return null; // 或者抛出异常
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int numNodes = 5;
        List edges = new ArrayList<>();

        // 示例图，包含负权边
        edges.add(new Edge(0, 1, -1));
        edges.add(new Edge(0, 2, 4));
        edges.add(new Edge(1, 2, 3));
        edges.add(new Edge(1, 3, 2));
        edges.add(new Edge(1, 4, 2));
        edges.add(new Edge(3, 2, 5));
        edges.add(new Edge(3, 1, 1));
        edges.add(new Edge(4, 3, -3)); // 负权边

        BellmanFordShortestPath solver = new BellmanFordShortestPath();
        int startNode = 0;
        int[] shortestDistances = solver.bellmanFord(edges, numNodes, startNode);

        if (shortestDistances != null) {
            System.out.println("从节点 " + startNode + " 到其他节点的最短距离 (Bellman-Ford):");
            for (int i = 0; i < numNodes; i++) {
                if (shortestDistances[i] == Integer.MAX_VALUE) {
                    System.out.println("到节点 " + i + ": 无法到达");
                } else {
                    System.out.println("到节点 " + i + ": " + shortestDistances[i]);
                }
            }
        }

        // 负环示例：
        System.out.println("\n--- 负环检测示例 ---");
        List negativeCycleEdges = new ArrayList<>();
        negativeCycleEdges.add(new Edge(0, 1, 1));
        negativeCycleEdges.add(new Edge(1, 2, -1));
        negativeCycleEdges.add(new Edge(2, 0, -1)); // 0 -> 1 -> 2 -> 0, 总和 1 - 1 - 1 = -1 (负环)

        int[] negativeCycleDist = solver.bellmanFord(negativeCycleEdges, 3, 0);
        // 预期输出：图中存在负环！最短路径无法确定。
    }
}

Bellman-Ford的时间复杂度是O(V*E)，V是节点数，E是边数。这比Dijkstra的O(E log V)或O(E + V log V)要慢，但它能处理负权边，这就是它的价值所在。在实现时，我通常会用一个List来存储所有的边，这样在每次迭代中可以方便地遍历所有边。

多源最短路径：Floyd-Warshall算法在Java中的应用场景与代码结构

当你的需求是找出图中所有节点对之间的最短路径时，Floyd-Warshall算法就闪亮登场了。这算法非常优雅，因为它基于动态规划的思想，代码结构也相对简洁。它同样能处理负权边，但和Bellman-Ford一样，它无法处理负环（如果存在负环，它会给出不正确的结果，但不会像Bellman-Ford那样明确告诉你存在负环）。

Floyd-Warshall的核心是“中间节点”的概念。它通过迭代所有可能的中间节点k，来尝试更新所有i到j的最短路径。

import java.util.Arrays;

public class FloydWarshallShortestPath {

    // Floyd-Warshall算法实现
    public int[][] floydWarshall(int[][] graph, int numNodes) {
        int[][] dist = new int[numNodes][numNodes];

        // 初始化距离矩阵
        // dist[i][j] = graph[i][j] (如果存在边)
        // dist[i][j] = 无穷大 (如果不存在边且 i != j)
        // dist[i][i] = 0
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                if (i == j) {
                    dist[i][j] = 0;
                } else if (graph[i][j] != 0) { // 假设0表示没有直接边，或者根据实际情况用一个特殊值
                    dist[i][j] = graph[i][j];
                } else {
                    dist[i][j] = Integer.MAX_VALUE; // 表示不可达
                }
            }
        }

        // 核心三重循环
        // k 是中间节点
        // i 是起点
        // j 是终点
        for (int k = 0; k < numNodes; k++) {
            for (int i = 0; i < numNodes; i++) {
                for (int j = 0; j < numNodes; j++) {
                    // 避免溢出：如果 dist[i][k] 或 dist[k][j] 是 MAX_VALUE，则跳过
                    if (dist[i][k] != Integer.MAX_VALUE && dist[k][j] != Integer.MAX_VALUE) {
                        // 如果通过k点中转，路径更短
                        if (dist[i][k] + dist[k][j] < dist[i][j]) {
                            dist[i][j] = dist[i][k] + dist[k][j];
                        }
                    }
                }
            }
        }

        // 可选：检测负环
        // 如果对角线元素 dist[i][i] 变为负数，则存在负环
        for (int i = 0; i < numNodes; i++) {
            if (dist[i][i] < 0) {
                System.out.println("图中存在负环！");
                // 可以选择在这里返回null或抛出异常
            }
        }

        return dist;
    }

    public static void main(String[] args) {
        int numNodes = 4;
        // 使用邻接矩阵表示图
        // 0表示没有直接边，或者用一个非常大的数表示无穷大
        int[][] graph = {
            {0, 3, Integer.MAX_VALUE, 7},
            {8, 0, 2, Integer.MAX_VALUE},
            {5, Integer.MAX_VALUE, 0, 1},
            {2, Integer.MAX_VALUE, Integer.MAX_VALUE, 0}
        };

        // 这里的Integer.MAX_VALUE代表无穷大，也可以用一个足够大的数，比如100000000
        // 实际使用时要确保这个值不会和真实的路径长度混淆，且不会导致溢出

        FloydWarshallShortestPath solver = new FloydWarshallShortestPath();
        int[][] allPairsShortestPaths = solver.floydWarshall(graph, numNodes);

        System.out.println("所有节点对之间的最短距离 (Floyd-Warshall):");
        for (int i = 0; i < numNodes; i++) {
            for (int j = 0; j < numNodes; j++) {
                if (allPairsShortestPaths[i][j] == Integer.MAX_VALUE) {
                    System.out.print("INF\t");
                } else {
                    System.out.print(allPairsShortestPaths[i][j] + "\t");
                }
            }
            System.out.println();
        }
        // 预期输出：
        // 0    3   5   6
        // 8    0   2   3
        // 5    8   0   1
        // 2    5   7   0
    }
}

Floyd-Warshall的时间复杂度是固定的O(V^3)，V是节点数。这对于节点数量不大的图（比如几百个节点）来说是可接受的，但如果节点数量上千，那可能就太慢了。它的优点是代码简单，易于理解和实现，而且能直接得到所有节点对的最短路径。初始化时，通常会用Integer.MAX_VALUE来表示两个节点之间没有直接路径，或者路径无限长。在计算dist[i][k] + dist[k][j]时，务必检查dist[i][k]和dist[k][j]是否为Integer.MAX_VALUE，否则直接相加会导致溢出。

图数据结构的选择：邻接矩阵与邻接表的Java实践考量

在Java中实现图算法，最基础的决策就是如何表示图。我通常在这两者之间权衡：邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。这就像选择工具