java代码怎样实现图的最短路径算法 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<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<Pair> 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<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 4->1)        // 到节点 2: 9 (0->4->1->2)        // 到节点 3: 7 (0->4->3)        // 到节点 4: 5 (0->4)    }}

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

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

立即学习“Java免费学习笔记（深入）”；

在Java中实现Dijkstra，最关键的是数据结构的选择。我通常会用

List<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("INFt");                } 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）。这就像选择工具

以上就是java代码怎样实现图的最短路径算法 java代码图算法的实用实现技巧的详细内容，更多请关注创想鸟其它相关文章！