要么改变世界,要么适应世界

Bellman-Ford算法模板

2021-04-24 17:51:54
74
目录

Bellman-FordDijkstra 算法一样,也是用于求带权图的最短路,不过与后者相比,前者可以解决边权为负数的情况,适应性较强;

算法主要的流程是对每一个点根据边进行松弛操作,最终求得最优解的过程。

算法的时间复杂度是O(V*E)

/*
 * @Author      : YaleXin
 * @Email       : me@yalexin.top
 * @LastEditors : YaleXin
 */
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int MAX_N = 1501, MAX_M = 5e4 + 1, INF = 0x7f7f7f7f, START = 1;
int n, m, minD[MAX_N], pre[MAX_N];
struct Edge{
    int u, v, w;
}edges[MAX_M];
// 快读
int read(){
    int sum = 0;
    bool ok = false;
    char ch = getchar();
    while(ch < '0' || ch > '9'){
        if (ch == '-')ok = true;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9'){
        sum = (sum << 1) + (sum << 3) + ch - '0';
        ch = getchar();
    }
    return ok ? -sum : sum;
}
void dfs(int son){
    if (son != pre[son]){
        dfs(pre[son]);
        cout << "->" << flush;
        cout << son << flush;
    } else{
        cout << son << flush;
    }
}
void print_path(int root) {
    while (root != pre[root]) {
        printf("%d-->", root);
        root = pre[root];
    }
    if (root == pre[root]) printf("%d\n", root);
}

void print(){
    for(int i = 1; i <= n; i++){
        cout << "nodeId: " << i << ", minLen : " << minD[i] << ", path : " << ends;
        dfs(i);
        cout << endl;
    }
}
// 不存在负环的时候,minD中保存的就是从起始点到各个点的最短路权值
bool Bellman_Ford(){
    memset(minD, 0x7f, sizeof minD);
    minD[START] = 0, pre[START] = START;
    int u, v, w;
    for(int i = 1; i < n; i++)
        for(int j = 1; j <= m; j++){
            u = edges[j].u, v = edges[j].v, w = edges[j].w;
            if (minD[u] + w < minD[v]){
                minD[v] = minD[u] + w;
                pre[v] = u;
            }
        }
    bool ok = true;  //判断是否含有负权回路
    for (int i = 1; i <= m; ++i)
        if (minD[edges[i].v] > minD[edges[i].u] + edges[i].w) {
            ok = false;
            break;
        }
    return ok;
}
int main(){
    n = read(), m = read();
    int u, v, w;
    for (int i = 1; i <= m; i++){
        // 有向图
        u = read(), v = read(), w = read();
        edges[i].u = u, edges[i].v = v, edges[i].w = w;
    }
    if (Bellman_Ford()){
        print();
    } else{
        cout << "not exit!" << endl;
    }
    return 0;
}
/*
5 7
1 2 5
1 3 5
2 5 -1
2 3 -2
3 4 3
3 5 -2
4 5 2



5 7
1 2 1
2 4 2
5 4 3
3 4 4
1 3 5
1 5 6
2 5 7
*/

这部分的代码尤为重要:

bool ok = true;  //判断是否含有负权回路
for (int i = 1; i <= m; ++i)
    if (minD[edges[i].v] > minD[edges[i].u] + edges[i].w) {
        ok = false;
        break;
    }

如果存在从源点可达的权为负的回路,那么我就可以不断地通过使用这一条回路将路径长度缩小,即最小路径和不收敛,哪来的最短路?

历史评论
开始评论