最短路算法：Dijkstra 与 Bellman-Ford

Dijkstra 算法（有向带权图，无负权）

贪心 + 小顶堆，每次从未访问节点中取最短距离节点：

public int[] dijkstra(int n, int[][] edges, int src) {
    // 建邻接表
    List<int[]>[] graph = new List[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    for (int[] e : edges) graph[e[0]].add(new int[]{e[1], e[2]});

    int[] dist = new int[n];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[src] = 0;
    // [cost, node]
    PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[0]));
    pq.offer(new int[]{0, src});
    while (!pq.isEmpty()) {
        int[] cur = pq.poll();
        int cost = cur[0], node = cur[1];
        if (cost > dist[node]) continue;  // 已找到更短路径，跳过
        for (int[] next : graph[node]) {
            int nDist = dist[node] + next[1];
            if (nDist < dist[next[0]]) {
                dist[next[0]] = nDist;
                pq.offer(new int[]{nDist, next[0]});
            }
        }
    }
    return dist;
}

LeetCode 743 - 网络延迟时间：

public int networkDelayTime(int[][] times, int n, int k) {
    int[] dist = dijkstra(n + 1, times, k);  // 节点 1-indexed
    int max = 0;
    for (int i = 1; i <= n; i++) {
        if (dist[i] == Integer.MAX_VALUE) return -1;
        max = Math.max(max, dist[i]);
    }
    return max;
}

Bellman-Ford 算法（允许负权，检测负环）

对所有边松弛 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;
    for (int i = 0; i < n - 1; i++) {
        for (int[] e : edges) {
            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;
        }
    }
    // 检测负环
    for (int[] e : edges) {
        if (dist[e[0]] != Integer.MAX_VALUE && dist[e[0]] + e[2] < dist[e[1]])
            return null; // 存在负环
    }
    return dist;
}

Floyd-Warshall（多源最短路）

任意两点最短路径，O(n³)，适合稠密图：

public int[][] floydWarshall(int n, int[][] edges) {
    int[][] dp = new int[n][n];
    for (int[] row : dp) Arrays.fill(row, Integer.MAX_VALUE / 2);
    for (int i = 0; i < n; i++) dp[i][i] = 0;
    for (int[] e : edges) dp[e[0]][e[1]] = Math.min(dp[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++)
                dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k][j]);
    return dp;
}

总结