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("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）。这就像选择工具
