如何实现Bellman-Ford最短路径算法？

Bellman-Ford 算法也是一种找到图中所有节点到某个节点的最短路径的算法。
我们可以使用邻接表实现 Bellman-Ford 算法:

public int[] bellmanFord(List<Edge>[] graph, int start) {
    int n = graph.length;
    int[] dist = new int[n];
    for (int i = 0; i < n; i++) dist[i] = Integer.MAX_VALUE;
    dist[start] = 0;

    for (int i = 0; i < n - 1; i++) {  // n-1 次松弛操作
        for (List<Edge> adj : graph) {
            for (Edge e : adj) {
                if (dist[e.from] != Integer.MAX_VALUE && dist[e.from] + e.weight < dist[e.to]) {
                    dist[e.to] = dist[e.from] + e.weight;
                }
            }
        }
    }

    // 检测负权环
    for (List<Edge> adj : graph) {
        for (Edge e : adj) {
            if (dist[e.from] != Integer.MAX_VALUE && dist[e.from] + e.weight < dist[e.to]) {
                return new int[]{-1};   // 存在负权环
            }
        }
    }

    return dist;
}

Bellman-Ford 算法流程:

1. 构建数组 dist 记录所有节点到 start 节点的最短距离,初始为 MAX_VALUE。start 节点距离为 0。
2. 进行 n-1 次松弛操作。遍历所有边,如果通过该边可以得到更短的路径则更新 dist。
3. 再进行一次松弛操作,检测是否存在负权环。如果存在则返回 -1。
4. 返回 dist 数组,得到所有节点到 start 节点的最短路径。

时间复杂度 O(n^2),空间复杂度 O(n)。

所以,Bellman-Ford 算法的关键是:

1. 构建数组 dist 记录所有节点到起点的最短距离,初始为最大值。
2. 进行 n-1 次松弛操作,更新各节点的最短距离。
3. 进行一次松弛操作检测负权环。如果存在则返回 -1。
4. 返回 dist 数组,得到所有节点到起点的最短路径。