算法刷题系列（四十一）：最短路——按边权条件选择算法

算法刷题系列（四十一）：最短路——按边权条件选择算法

最短路不是单一算法题型。边是否带权、权重能否为负、图有多大，会直接决定合适的算法。把条件判断放在写代码之前，往往比背下某个模板更重要。

图的条件	常用算法	时间复杂度（典型表示）	关键限制
无权图，或每条边代价相同	BFS	O(V + E)	按边数最少即按总代价最小
非负边权	Dijkstra + 最小堆	O((V + E) log V)	不能有负权边
存在负边，且没有可达负环	Bellman-Ford	O(VE)	较慢；可检测负环

如果存在一条从源点可达的负权环，沿环绕行可以无限降低路径代价，“最短距离”没有有限答案。负环若不可从源点到达，则不影响从该源点出发的结果。

三种算法如何维护状态

BFS：队列按层处理顶点。第一次到达某个顶点时，使用的边数最少；当每条边权相同时，这也就是总代价最小。将顶点标记为已发现后再入队，避免重复排队。

Dijkstra：dist[v] 是当前已知的源点到 v 的最小代价。优先队列每次取出距离最小的候选；在非负权条件下，取出的有效最小距离已经不可能被之后的路径改小。实现用“过期条目跳过”处理优先队列不支持 decrease-key 的情况。

Bellman-Ford：重复扫描所有边，尝试用 dist[u] + w 改善 dist[v]。任意最短简单路径最多含 V - 1 条边，所以最多进行 V - 1 轮松弛；再扫描一轮仍能变小，就存在从源点可达的负环。

以下两个版本返回距离数组；不可达位置用 -1 表示。示例均检查输入端点，Dijkstra 会拒绝负权边。

Java 实现

import java.util.*;

public class Main {
    static class Edge {
        int from, to;
        long weight;
        Edge(int from, int to, long weight) {
            this.from = from; this.to = to; this.weight = weight;
        }
    }
    static class State {
        int node;
        long distance;
        State(int node, long distance) { this.node = node; this.distance = distance; }
    }

    static void validate(int n, int source, Edge[] edges) {
        if (n < 0 || edges == null || (n > 0 && (source < 0 || source >= n)))
            throw new IllegalArgumentException("invalid graph");
        for (Edge e : edges) {
            if (e == null || e.from < 0 || e.from >= n || e.to < 0 || e.to >= n)
                throw new IllegalArgumentException("invalid edge");
        }
    }

    static long[] bfs(int n, int source, Edge[] edges) {
        validate(n, source, edges);
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (Edge e : edges) graph.get(e.from).add(e.to);
        long[] dist = new long[n];
        Arrays.fill(dist, -1);
        if (n == 0) return dist;
        ArrayDeque<Integer> queue = new ArrayDeque<>();
        dist[source] = 0;
        queue.add(source);
        while (!queue.isEmpty()) {
            int u = queue.remove();
            for (int v : graph.get(u)) {
                if (dist[v] == -1) {
                    dist[v] = dist[u] + 1;
                    queue.add(v);
                }
            }
        }
        return dist;
    }

    static long[] dijkstra(int n, int source, Edge[] edges) {
        validate(n, source, edges);
        List<List<Edge>> graph = new ArrayList<>();
        for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
        for (Edge e : edges) {
            if (e.weight < 0) throw new IllegalArgumentException("Dijkstra requires nonnegative weights");
            graph.get(e.from).add(e);
        }
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        if (n == 0) return dist;
        PriorityQueue<State> pq = new PriorityQueue<>(Comparator.comparingLong(s -> s.distance));
        dist[source] = 0;
        pq.add(new State(source, 0));
        while (!pq.isEmpty()) {
            State cur = pq.remove();
            if (cur.distance != dist[cur.node]) continue;
            for (Edge e : graph.get(cur.node)) {
                long next = cur.distance + e.weight;
                if (next < dist[e.to]) {
                    dist[e.to] = next;
                    pq.add(new State(e.to, next));
                }
            }
        }
        for (int i = 0; i < n; i++) if (dist[i] == Long.MAX_VALUE) dist[i] = -1;
        return dist;
    }

    // 返回 null 表示存在从 source 可达的负环；否则返回距离（不可达为 -1）。
    static long[] bellmanFord(int n, int source, Edge[] edges) {
        validate(n, source, edges);
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        if (n == 0) return dist;
        dist[source] = 0;
        for (int round = 1; round < n; round++) {
            boolean changed = false;
            for (Edge e : edges) {
                if (dist[e.from] != Long.MAX_VALUE
                        && dist[e.from] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[e.from] + e.weight;
                    changed = true;
                }
            }
            if (!changed) break;
        }
        for (Edge e : edges) {
            if (dist[e.from] != Long.MAX_VALUE
                    && dist[e.from] + e.weight < dist[e.to]) return null;
        }
        for (int i = 0; i < n; i++) if (dist[i] == Long.MAX_VALUE) dist[i] = -1;
        return dist;
    }

    public static void main(String[] args) {
        Edge[] edges = {new Edge(0, 1, 4), new Edge(0, 2, 1),
                        new Edge(2, 1, 2), new Edge(1, 3, 1)};
        System.out.println(Arrays.toString(dijkstra(4, 0, edges))); // [0, 3, 1, 4]
        System.out.println(Arrays.toString(bfs(4, 0, edges)));     // [0, 1, 1, 2]
        Edge[] negative = {new Edge(0, 1, 3), new Edge(1, 2, -2)};
        System.out.println(Arrays.toString(bellmanFord(3, 0, negative))); // [0, 3, 1]
    }
}

Python 实现

from collections import deque
from heapq import heappop, heappush
from typing import Optional

def bfs(n: int, source: int, edges: list[tuple[int, int, int]]) -> list[int]:
    graph = [[] for _ in range(n)]
    for u, v, _ in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint out of range")
        graph[u].append(v)
    if n == 0:
        return []
    if not 0 <= source < n:
        raise ValueError("source out of range")
    dist = [-1] * n
    dist[source] = 0
    queue = deque([source])
    while queue:
        u = queue.popleft()
        for v in graph[u]:
            if dist[v] == -1:
                dist[v] = dist[u] + 1
                queue.append(v)
    return dist

def dijkstra(n: int, source: int, edges: list[tuple[int, int, int]]) -> list[int]:
    graph = [[] for _ in range(n)]
    for u, v, weight in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint out of range")
        if weight < 0:
            raise ValueError("Dijkstra requires nonnegative weights")
        graph[u].append((v, weight))
    if n == 0:
        return []
    if not 0 <= source < n:
        raise ValueError("source out of range")
    dist = [float("inf")] * n
    dist[source] = 0
    heap = [(0, source)]
    while heap:
        current, u = heappop(heap)
        if current != dist[u]:
            continue
        for v, weight in graph[u]:
            candidate = current + weight
            if candidate < dist[v]:
                dist[v] = candidate
                heappush(heap, (candidate, v))
    return [-1 if value == float("inf") else value for value in dist]

def bellman_ford(n: int, source: int, edges: list[tuple[int, int, int]]) -> Optional[list[int]]:
    if n == 0:
        return []
    if not 0 <= source < n:
        raise ValueError("source out of range")
    for u, v, _ in edges:
        if not (0 <= u < n and 0 <= v < n):
            raise ValueError("edge endpoint out of range")
    dist = [float("inf")] * n
    dist[source] = 0
    for _ in range(n - 1):
        changed = False
        for u, v, weight in edges:
            if dist[u] != float("inf") and dist[u] + weight < dist[v]:
                dist[v] = dist[u] + weight
                changed = True
        if not changed:
            break
    if any(dist[u] != float("inf") and dist[u] + w < dist[v] for u, v, w in edges):
        return None  # 可达负环
    return [-1 if value == float("inf") else value for value in dist]

weighted = [(0, 1, 4), (0, 2, 1), (2, 1, 2), (1, 3, 1)]
assert dijkstra(4, 0, weighted) == [0, 3, 1, 4]
assert bfs(4, 0, weighted) == [0, 1, 1, 2]
assert bellman_ford(3, 0, [(0, 1, 3), (1, 2, -2)]) == [0, 3, 1]
assert bellman_ford(3, 0, [(0, 1, 1), (1, 1, -1)]) is None

边界与常见误区

BFS 适用于无权图，也适用于所有边权相同的图；若边权虽非负但不相同，不可把 BFS 的层数当作总权重。Dijkstra 的“取出即确定”依赖非负边，遇到负权边应改用 Bellman-Ford（或满足特定结构时使用其他算法）。Bellman-Ford 检测负环时必须忽略不可达起点，否则不可达负环会被误报。上述代码按有向边处理；无向边要在邻接结构中添加两个方向。实际实现还应根据权重范围选择足够宽的整数类型。

小结

先看边的权重条件，再选算法：等权用 BFS，非负权用 Dijkstra，含负权时用 Bellman-Ford 并检查可达负环。算法选择正确，状态更新才有可靠的正确性依据。