Problem6454--学习系列 —— 图论:Bellman-Ford 算法

6454: 学习系列 —— 图论:Bellman-Ford 算法

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 256 MiB

Description

是单源最短路问题求救算法之一。
【适用范围】
1、能求解带负权边的最短路径。但是在竞赛中,碰到负权图,我们一般使用 SPFA 算法,因为大部分情况下 SPFA 速度更快。
2、可以判断图中是否有环。但是一般使用 SPFA 算法。
3、碰到只能经过 $m$ 条边组成的最短路问题,就只能使用本算法解决。
【时间复杂度】
存在 $|V|$ 次对边集合的迭代松弛,边集合的大小为 $|E|$,所以Bellman-Ford 算法的时间复杂度为 $O(|V||E|)$。
【实现思想】
其实现方式是通过 $m$ 次迭代求出从源点到终点不超过 $m$ 条边构成的最短路的路径。很重要的一点是每次迭代都是在上一次的基础上进行的,因此我们在代码实现时要注意保留上一次的结果,在上一次的基础上算。
【图解过程】




【实现细节】
1. 图存储使用链式前向星方式,存储每一条边。
2. 在本次松弛操作的时候,务必使用上一轮的数据。
【模板代码】
const LL INF=0x3f3f3f3f3f3f3f3f;
//顶点相关数据
const int N=1e3+10;
LL dis[N];//距离
LL backup[N];//上一轮距离
//保存所有的边
const int M=1e3+10;
struct EDGE {
    LL u,v,w;
} a[M];

LL K;//最多包含K条边
LL m;//边的数量
//st 是起点
void bellman-ford(LL st) {
    memset(dis, 0x3f, sizeof dis);//将距离设置为无穷大
    dis[st]=0;

    for (LL i=1; i<=K; i++) {
        //通过这个实现使用上一轮数据进行迭代
        memcpy(backup, dis, sizeof dis);

        //遍历所有边进行迭代
        for (LL i=1; i<=m; i++) {
            //u->v w
            LL u=a[j].u;
            LL v=a[j].v;
            LL w=a[j].w;
            if (dis[v]>backup+w) {
                dis[v]=backup+w;
        }
    }
}

//下面是判断无穷大,因为可能有负权边
if (dis[n]>=INF/2) {
    //这里是无穷大
}

HINT

本题只是知识点讲解。
请不要尝试提交本题,否则你会得到 RE(Runtime Error)。

Source/Category