加载中…
应用场景：导航 · 网络路由
交互式动画演示，可调整参数并单步执行。
全屏打开最短路径问题：在带权图中，找到从源点 s 到目标点 t（或所有点）的路径，使得路径上边的权值之和最小。
| 变体 | 描述 |
|---|---|
| 单源最短路径（SSSP） | 从一个源点到所有其他点 |
| 单源到单点 | 从 s 到 t |
| 全源最短路径（APSP） | 任意两点之间 |
graph LR A -->|4| B A -->|1| C C -->|2| B B -->|1| D C -->|5| D
上图中 A→D 最短路径：A→C→B→D = 1+2+1 = 4（而非 A→B→D = 5）。
| 算法 | 适用场景 | 时间复杂度 | 负权边 | 负权环 |
|---|---|---|---|---|
| BFS | 无权图 | O(V + E) | ❌ | ❌ |
| Dijkstra | 非负权图 | O((V+E) log V) | ❌ | ❌ |
| Bellman-Ford | 通用（可检测负环） | O(VE) | ✅ | 检测 |
| SPFA | Bellman-Ford 优化 | 平均 O(kE)，最坏 O(VE) | ✅ | 检测 |
| Floyd-Warshall | 全源、稠密图 | O(V³) | ✅ | 检测 |
贪心：每次从未确定的点中选距离最小的，确定后不再更改。
前提：所有边权 ≥ 0。
public int[] dijkstra(List<int[]>[] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// {距离, 节点}
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
pq.offer(new int[]{0, src});
while (!pq.isEmpty()) {
int[] cur = pq.poll();
int d = cur[0], u = cur[1];
if (d > dist[u]) continue; // 已确定，跳过
for (int[] edge : graph[u]) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
pq.offer(new int[]{dist[v], v});
}
}
}
return dist;
}负权边可能使"已确定"的点距离再次变小，破坏贪心的正确性。
反例：A→B(2), A→C(3), C→B(-2) → B 的真实最短是 1，但 Dijkstra 先确定 B=2。
对所有边松弛 V-1 轮。如果第 V 轮还能松弛，说明存在负权环。
public int[] bellmanFord(int n, int[][] edges, int src) {
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
// 松弛 V-1 轮
for (int i = 0; i < n - 1; i++) {
boolean updated = false;
for (int[] e : edges) { // e = {from, to, weight}
int u = e[0], v = e[1], w = e[2];
if (dist[u] != Integer.MAX_VALUE && dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
updated = true;
}
}
if (!updated) break; // 提前终止
}
// 检测负权环
for (int[] e : edges) {
if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]]) {
throw new RuntimeException("存在负权环");
}
}
return dist;
}public int[] spfa(List<int[]>[] graph, int src) {
int n = graph.length;
int[] dist = new int[n];
Arrays.fill(dist, Integer.MAX_VALUE);
dist[src] = 0;
boolean[] inQueue = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(src);
inQueue[src] = true;
while (!queue.isEmpty()) {
int u = queue.poll();
inQueue[u] = false;
for (int[] edge : graph[u]) {
int v = edge[0], w = edge[1];
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (!inQueue[v]) {
queue.offer(v);
inQueue[v] = true;
}
}
}
}
return dist;
}DP 思想：dist[i][j] 表示只经过编号 ≤ k 的中间点时，i 到 j 的最短距离。
转移：dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
public int[][] floyd(int n, int[][] edges) {
int[][] dist = new int[n][n];
for (int[] row : dist) Arrays.fill(row, Integer.MAX_VALUE / 2);
for (int i = 0; i < n; i++) dist[i][i] = 0;
for (int[] e : edges) {
dist[e[0]][e[1]] = Math.min(dist[e[0]][e[1]], e[2]);
}
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
}
}
}
return dist;
}graph TD
Q1{有负权边?} -->|否| Q2{单源还是全源?}
Q1 -->|是| Q3{需要全源?}
Q2 -->|单源| D[Dijkstra]
Q2 -->|全源| F[Floyd]
Q3 -->|是| F
Q3 -->|否| BF[Bellman-Ford / SPFA]
| 场景 | 推荐 |
|---|---|
| 非负权 + 单源 | Dijkstra（堆优化） |
| 有负权 + 单源 | Bellman-Ford / SPFA |
| 全源 + 点少（V≤500） | Floyd |
| 无权图 | BFS |
| 需要检测负环 | Bellman-Ford |
Dijkstra 中记录前驱：
int[] prev = new int[n];
Arrays.fill(prev, -1);
// 松弛时：
if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
prev[v] = u;
pq.offer(new int[]{dist[v], v});
}
// 还原路径
List<Integer> path = new ArrayList<>();
for (int cur = target; cur != -1; cur = prev[cur]) {
path.add(cur);
}
Collections.reverse(path);dist[src] = 0，其余为 INF（用 Integer.MAX_VALUE / 2 防溢出）。if (d > dist[u]) continue 不能省，否则超时。