跳到主要内容

图的最短路径

最短路径问题是指在加权图中寻找两个顶点之间权值之和最小的路径。

单源最短路径​

已知起点，求该点到其他所有顶点的最短距离。

1. Dijkstra 算法 (贪心思想)​

核心步骤：

  1. 从未访问顶点中找距离为最小的。
  2. 以其为中转点，更新其他邻接顶点的距离。

限制：不能处理负权边。

复杂度：

  • 朴素实现：O(V²)
  • 优先队列优化：O(E log V)
public int[] dijkstra(int start) {
    int[] dist = new int[V];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[start] = 0;
    PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    pq.offer(new int[]{start, 0});
    while (!pq.isEmpty()) {
        int[] curr = pq.poll();
        int u = curr[0], d = curr[1];
        if (d > dist[u]) continue;
        for (Edge e : graph.adj[u]) {
            if (dist[u] + e.weight < dist[e.to]) {
                dist[e.to] = dist[u] + e.weight;
                pq.offer(new int[]{e.to, dist[e.to]});
            }
        }
    }
    return dist;
}

2. Bellman-Ford 算法 (松弛操作)​

核心：对所有边连续进行 V-1 次松弛操作。 限制：可以处理负权边，但不能包含负环（通过第 V 次松弛检测负环）。

多源最短路径​

求任意两点之间的最短距离。

Floyd-Warshall 算法 (动态规划)​

核心：尝试通过每一个顶点 kk 作为中转点，看能否缩短 ii 到 jj 的路径。 复杂度：O(V³) 时间，O(V²) 空间。

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]);
        }
    }
}

练习​

  1. LeetCode 743：网络延迟时间 (Dijkstra)
  2. LeetCode 1334：阈值距离内邻居数量最少的城市 (Floyd)
  3. LeetCode 787：K 站中转内最便宜的航班 (Bellman-Ford 变体)
  4. 理解 “松弛 (Relaxation)” 的概念。