最短路径问题

求一个点到其他点的最短路径

1. Bellman-Ford 算法

需要条件：

没有负根，即点到点之间的距离不会出现负数的情况，这种情况会造成死循环
可以有环，即几个点之间可以连成环

思路：

一直循环，知道每个点都是最佳的点
每次循环时都要遍历已知的边一次，判断用上这条边能否使点更近
当循环一遍后都没有使点更近的边，则结束循环

模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27


// d[i] 表示从起点到 i 的最短距离
// f[i] = {pos1, pos2, len}，表示从 pos1 到 pos2 这条边的长度，已知

int INF = 0X3f3f3f3f;
void shortPath(int start) {
    // 初始化所有点的距离
    for (int i = 0; i < n; i++) {
        d[i] = INF;
    }
    d[start] = 0;

    // 循环
    while (true) {
        boolean update = false;
        // 遍历每条题目给的边
        for (int[] bian : f) {
            if (d[bian[0]] != INF && d[bian[1]] > d[bian[0]] + bian[2]) {
                d[bian[1]] = d[bian[0]] + bian[2];
                update = true;
            }
        }
        if (!update) {
            // 终止条件，本次循环中没有点发生改变
            break;
        }
    }
}

时间复杂度：O(n²)
空间复杂度：O(n)

2. Dijkstra 算法

需要条件：

没有负根
可以有环

思路：

若已知一个点的最短距离后，将与其向临近的点以及到点的距离放到最小堆里
每次都是从最小堆中取点
同时设置一个 visited 数组，查看是否已经使用过

模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22


// d[i][j] 表示从 i 到 j 的边的长度
void shortPath(int start) {
    // int[]: [len, pos]
    PriorityQueue<int[]> pq = new PriorityQueue<>((x, y) -> {
        return x[0] - y[0];
    });
    // 将起点放进去，此时到起点的距离为 0
    pq.offer(new int[]{0, start});
    // 起点已经使用过了，标记起来
    boolean[] visited = new boolean[n];
    visited[start] = true;

    while (!pq.isEmpty()) {
        int[] f = pq.poll();
        for (int i = 0; i < n; i++) {
            // 此点没用过，并且有边
            if (!visited[i] && d[f[1]][i] != INF) {
                queue.offer(new int[]{f[0] + d[f[1]][i], i});
            }
        }
    }
}

时间复杂度：O(nlog(n))
空间复杂度：O(n)

所有点到所有点之间的最短距离

Floyd 算法

需要条件：

可以为负根
可以有环

思路：动态规划

dp[i][j] = min(d[i][j], d[i][k] + dp[k][j])
d[i][k] + dp[k][j] 表示从 i 经过点 k 到 j 的距离

模板：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


// d[i][j] 表示从 i 到 j 的最短距离
// dp[i][j] 表示 i 到 j 的边的长度
void shortPath() {
    // k 要放在前面！！
    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                d[i][j] = min(d[i][j], d[i][k] + dp[k][j]);
            }
        }
    }
}

最短路径问题

求一个点到其他点的最短路径

1. Bellman-Ford 算法

2. Dijkstra 算法

所有点到所有点之间的最短距离

Floyd 算法

相关文章：