图的最短路径—Floyd算法和Bellman-Ford算法

发表于 更新于 分类于 阅读次数： 本文字数： 1k 阅读时长 ≈ 2 分钟

Floyd算法

借助邻接矩阵辅助，Floyd算法可以解决数据量不大，且权值中有负数的图，但不能是存在负环的图的最短路径问题。该算法步骤如下：

  1. 在n个节点中寻找”跳点”bridge
  2. 如果graph[from][bridge] != INT_MAX && graph[bridge][to] != INT_MAX && graph[from][bridge] + graph[bridge][to] < graph[from][to] 则更新邻接矩阵
1
2
3
4
5
6
7
8
9
10
for (int bridge = 0; bridge < n; ++bridge) {
    for (int from = 0; from < n; ++from)
        for (int to = 0; to < n; ++to) {
            if (graph[from][bridge] != INT_MAX &&
                graph[bridge][to] != INT_MAX &&
                graph[from][bridge] + graph[bridge][to] < graph[from][to]) {
                    graph[from][to] = graph[from][bridge] + graph[bridge][to];
                }
    }
}

显而易见，floyd算法的时间复杂度是O(n^3) 空间复杂度是O(n^2)

Bellman-Ford算法

Bellman-Ford 可以解决权值中存在负数，但不能存在负环的图，找出任意两点的最短路径问题。该算法步骤如下：

  1. 初始化distance数组 即vector<int>distance(n, INT_MAX);
  2. 对所有边进行n-1的“松弛”（取最小值）操作

算法模版如下：

1
2
3
4
5
6
7
8
9
10
vector<int> distance(n, INT_MAX);
distance[0] = 0; // 源点设为0

for (int i = 0; i < n; ++i)
    for (auto edge : edges) {
        int from = edge[0], to = edge[1], weight = edge[2];
        if (distance[from] != INT_MAX) {
            distance[to] = min(distance[to], distance[from] + weight);
        }
    }

Bellman-Ford算法的时间复杂度为 O(n^2) 空间复杂度为O(n)