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 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], 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>> adj = new ArrayList();
for (int i = 0; i ());
}
// 添加边：(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)
}
}</list></k></integer></pair></list>
单源最短路径：Dijkstra算法的Java实现细节与优化
Dijkstra算法是解决单源最短路径问题的不二之选，前提是图中没有负权边。它的核心在于一个贪婪策略：每次从“待处理”的节点中，选择当前距离起始点最近的那个。
在Java中实现Dijkstra，最关键的是数据结构的选择。我通常会用
List<list>></list>
来表示图的邻接表，其中
Edge
是一个自定义的类，包含目标节点和边的权重。这个选择在处理稀疏图时尤其高效，因为它只存储实际存在的边，不像邻接矩阵那样需要为所有可能的边分配空间。
另一个核心是
java.util.PriorityQueue
。这个优先队列是Dijkstra算法性能的关键。它能保证我们每次取出的都是当前距离起始点最近的未访问节点。队列里通常存的是一个
Pair<integer 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慢，但胜在能处理负权边，并且还能检测出负环。负环是个麻烦事儿，因为它意味着某些路径可以无限缩短，导致最短路径没有定义。
AI 舌诊面诊问诊医疗系统 + 诊疗商城系统源码是一套结合 AI 辅助诊断与商品转化的健康类程序，基于浩创云、ThinkPHP（PHP）开发，支持微信服务号与 H5 端，适合做中医舌诊面诊问答、健康建议推送以及配套诊疗商品的运营。
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 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 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);
// 预期输出：图中存在负环！最短路径无法确定。
}
}</edge>
Bellman-Ford的时间复杂度是O(V*E)，V是节点数，E是边数。这比Dijkstra的O(E log V)或O(E + V log V)要慢，但它能处理负权边，这就是它的价值所在。在实现时，我通常会用一个
List<edge></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 <p>Floyd-Warshall的时间复杂度是固定的O(V^3)，V是节点数。这对于节点数量不大的图（比如几百个节点）来说是可接受的，但如果节点数量上千，那可能就太慢了。它的优点是代码简单，易于理解和实现，而且能直接得到所有节点对的最短路径。初始化时，通常会用</p><pre class="brush:php;toolbar:false;">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 大师之旅：从入门到精通的终极指南
