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<Edge>> 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<Integer, Integer>> pq = new PriorityQueue<>(Comparator.comparingInt(p -> p.getKey())); pq.offer(new Pair<>(0, startNode)); // 将起始节点加入队列 // 记录节点是否已被访问（即其最短路径是否已确定） boolean[] visited = new boolean[numNodes]; while (!pq.isEmpty()) { Pair<Integer, Integer> 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<K, V> { 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<Edge>> 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免费学习笔记（深入）”；
在Java中实现Dijkstra，最关键的是数据结构的选择。我通常会用
List<List<Edge>>
来表示图的邻接表，其中
Edge
是一个自定义的类，包含目标节点和边的权重。这个选择在处理稀疏图时尤其高效，因为它只存储实际存在的边，不像邻接矩阵那样需要为所有可能的边分配空间。
另一个核心是
java.util.PriorityQueue
。这个优先队列是Dijkstra算法性能的关键。它能保证我们每次取出的都是当前距离起始点最近的未访问节点。队列里通常存的是一个
Pair<Integer, Integer>
，第一个
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<Edge> 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<Edge> 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<Edge> 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<Edge>
来存储所有的边，这样在每次迭代中可以方便地遍历所有边。
多源最短路径：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）。这就像选择工具
