最短路算法 (bellman-Ford算法)

2023-01-04 17:01:40

贝尔曼-福特算法与迪科斯彻算法类似，都以松弛操作为基础，即估计的最短路径值渐渐地被更加准确的值替代，直至得到最优解。在两个算法中，计算时每个边之间的估计距离值都比真实值大，并且被新找到路径的最小长度替代。然而，迪科斯彻算法以贪心法选取未被处理的具有最小权值的节点，然后对其的出边进行松弛操作；而贝尔曼-福特算法简单地对所有边进行松弛操作，共|V | − 1次，其中 |V |是图的点的数量。在重复地计算中，已计算得到正确的距离的边的数量不断增加，直到所有边都计算得到了正确的路径。这样的策略使得贝尔曼-福特算法比迪科斯彻算法适用于更多种类的输入。

贝尔曼-福特算法的最多运行O（|V|·|E|)次，|V|和|E|分别是节点和边的数量）。

贝尔曼-福特算法与迪科斯彻算法最大的不同：bellman-Ford算法可以存在负权边，而dijkstra算法不允许出现负权边；

bellman-Ford算法的步骤：

　　　　步骤1：初始化图

　　　　步骤2 ：对每一条边进行松弛操作

　　　　步骤3：检查负权环

procedure BellmanFord(list vertices, list edges, vertex source)

   // 该实现读入边和节点的列表，并向两个数组（distance和predecessor）中写入最短路径信息

   // 步骤1：初始化图

   for each vertex v in vertices:

       if v is source then distance[v] :=

       else distance[v] := infinity

       predecessor[v] := null

   // 步骤2：重复对每一条边进行松弛操作

   for i from  to size(vertices)-:

       for each edge (u, v) with weight w in edges:

           if distance[u] + w < distance[v]:

               distance[v] := distance[u] + w

               predecessor[v] := u

   // 步骤3：检查负权环

   for each edge (u, v) with weight w in edges:

       if distance[u] + w < distance[v]:

           error "图包含了负权环"

POJ 3259

题意：John在N个农场之间有path与wormhole ，path+时间，wormhole-时间；求是否存在某点满足，John 旅行一些 paths和wormholes，回到原点时间为负。

思路：标准bellman-Ford算法；（检查负权环）

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <vector>

#include <queue>

#include <stack>

#include <set>

#define c_false ios_base::sync_with_stdio(false); cin.tie(0)

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3f

#define zero_(x,y) memset(x , y , sizeof(x))

#define zero(x) memset(x , 0 , sizeof(x))

#define MAX(x) memset(x , 0x3f ,sizeof(x))

#define swa(x,y) {LL s;s=x;x=y;y=s;}

using namespace std ;

#define N 505

#define lowbit(k) k&(-k)

const double PI = acos(-1.0);

const int M = 1e5+;

typedef long long LL ;

int farm, field, path, wormhole, sum;

int dis[N];

struct way{

    int Begin, End, Time;

}a[N*N];

bool BellmanFord(){

    for(int i = ; i <= field; i++) dis[i] = M;     ///初始化操作；

    for(int i = ; i <  field; i++){                ///松弛操作；

        for(int j = ; j <= sum; j++){

            if(dis[a[j].End] > dis[a[j].Begin] + a[j].Time)

               dis[a[j].End] = dis[a[j].Begin] + a[j].Time;

        }

    }

    for(int i = ; i <= sum; i++)                   ///检查负权环；

        if(dis[a[i].End] >dis[a[i].Begin] +a[i].Time)

            return false;

    return true;

}

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    //ios_base::sync_with_stdio(false); cin.tie(0);

    scanf("%d", &farm);

    while(farm--){

        int s, e, t, k = ;

        scanf("%d%d%d", &field, &path, &wormhole);

        for(int i = ; i < path; i++){

            scanf("%d%d%d", &s, &e, &t);

            k++;

            a[k].Begin = s;

            a[k].End   = e;

            a[k].Time  = t;

            k++;

            a[k].Begin = e;

            a[k].End   = s;

            a[k].Time  = t;

        }

        for(int i = ; i < wormhole; i++){

            scanf("%d%d%d", &s, &e, &t);

            k++;

            a[k].Begin = s;

            a[k].End   = e;

            a[k].Time  = -t;

        }

        sum = k;

        if(!BellmanFord()) printf("YES\n");

        else               printf("NO\n");

    }

    return ;

}

POj 1860

题意：N种货币，M个交易点，每次交易要收佣金，求是否存在增值的方法。

思路：刚好与Bellman-Ford算法相反，检查正权环；

A到B的边权为：B = (A - Cab)*Rab；

discuss里有人讨论环是否包含了S点，其实环没必要包含S点，

因为只要找到了一个可以无限增加财富的环，增加财富后再回到S点就可以了。

所以环是没必要包含S点的。

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <vector>

#include <queue>

#include <stack>

#include <set>

#define c_false ios_base::sync_with_stdio(false); cin.tie(0)

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3f

#define zero_(x,y) memset(x , y , sizeof(x))

#define zero(x) memset(x , 0 , sizeof(x))

#define MAX(x) memset(x , 0x3f ,sizeof(x))

#define swa(x,y) {LL s;s=x;x=y;y=s;}

using namespace std ;

#define N 505

#define lowbit(k) k&(-k)

const double PI = acos(-1.0);

const int M = 1e5+;

typedef long long LL;

int n, m, S, sum;

double Rab, Cab, Rba, Cba, V;

double dis[N];

struct way{

    int Begin, End;

    double Change, Rate;

}a[N*N];

bool BellmanFord(){

    zero(dis);

    dis[S] = V;

    int sign;

    for(int i = ; i <= n; i++){

        sign = ;

        for(int j = ; j <= sum; j++){

            if(dis[a[j].End] < (dis[a[j].Begin] - a[j].Change)*a[j].Rate)

               dis[a[j].End] = (dis[a[j].Begin] - a[j].Change)*a[j].Rate;

               sign = ;

        }

        if(!sign)

            break;

    }

    for(int j = ; j <= sum; j++){

            if(dis[a[j].End] < (dis[a[j].Begin] - a[j].Change)*a[j].Rate)

                return true;

    }

    return false;

}

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    //ios_base::sync_with_stdio(false); cin.tie(0);

    while(~scanf("%d%d%d%lf", &n, &m, &S, &V)){

        int x, y, k = ;

        for(int i = ; i < m; i++){

            scanf("%d%d%lf%lf%lf%lf", &x, &y, &Rab, &Cab,&Rba,&Cba);

            ++k;

            a[k].Begin = x;

            a[k].End   = y;

            a[k].Change= Cab;

            a[k].Rate  = Rab;

            ++k;

            a[k].Begin = y;

            a[k].End   = x;

            a[k].Change= Cba;

            a[k].Rate  = Rba;

        }

        sum = k;

        if(BellmanFord()) printf("YES\n");

        else              printf("NO\n");

    }

    return ;

}

POJ 1062

题意：酋长卖女儿，N个物品，阶级差判断是否连通，金币看作边权。求最小价格。（存在自己到自己的边）

设：dis[i] 为购买i物品需要的最小价格；pre[i] 为阶级；

初始化：dis[i] = prise; else INF;

边权：(A->B) B = A + dis[a[i].money];

关键在于阶级的判断：要保证以a[1]为终点的路径中满足阶级差不大于m；

　　　　　　　　　　开始以为边的两点都只要满足[pre[1] - m, pre[1] +m]就可以了；

　　　　　　　　　　但是如果边的两点的差值就直接大于m呢？(有人提出了越等级的要求！)

　　　　　　　　　　这时候就要满足全部[pre[1]-m,a[1]],[pre[1]-m+1, pre[1]+1]………[pre[1], pre[1] +m]；

　　　　　　　　　　对于每个物品先标记再求；取其最小值即可；

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <ctime>

#include <cmath>

#include <cstdio>

#include <string>

#include <cstring>

#include <vector>

#include <queue>

#include <stack>

#include <set>

#define c_false ios_base::sync_with_stdio(false); cin.tie(0)

#define INF 0x3f3f3f3f

#define INFL 0x3f3f3f3f3f3f3f3f

#define zero_(x,y) memset(x , y , sizeof(x))

#define zero(x) memset(x , 0 , sizeof(x))

#define MAX(x) memset(x , 0x3f ,sizeof(x))

#define swa(x,y) {LL s;s=x;x=y;y=s;}

using namespace std ;

#define N 505

#define lowbit(k) k&(-k)

const double PI = acos(-1.0);

const int M = 1e5+;

typedef long long LL;

int n, m, S, sum, P, L, X;

int dis[N],pre[N];

bool could[N];

struct way{

    int Begin, End, Money;

}a[N*N];

void BellmanFord(){

    for(int i = ; i <= n; i++)

        if(dis[i] == ) dis[i] = M;

    for(int i = ; i <= n; i++){

        for(int j = ; j <= sum; j++){

            if(could[a[j].End] && could[a[j].Begin])

                if(dis[a[j].End] > dis[a[j].Begin] + a[j].Money)

                   dis[a[j].End] = dis[a[j].Begin] + a[j].Money;

        }

    }

}

int main(){

    //freopen("in.txt","r",stdin);

    //freopen("out.txt","w",stdout);

    //ios_base::sync_with_stdio(false); cin.tie(0);

    while(~scanf("%d%d", &m, &n)){

        zero(dis);zero(pre);

        int x, y, k = ;

        for(int i = ; i <= n; i++){

            scanf("%d%d%d", &P, &L, &X);

            dis[i] = P;

            pre[i] = L;

            for(int j = ; j <= X; j++){

                scanf("%d%d", &x, &y);

                ++k;

                a[k].Begin = x;

                a[k].End   = i;

                a[k].Money = y;

            }

        }

        sum = k;

        int MIN = M;

        for(int i = ; i <= m; i++){

            zero(could);

            for(int j = ; j <= n; j++){

                if(pre[] - (m-i) <= pre[j] && pre[] + i >= pre[j]){

                    could[j] = true;

                    //cout<<pre[j]<<"  "<<j<<endl;

                }

            }

            BellmanFord();

            if(dis[] < MIN) MIN = dis[];

            //cout<<dis[1]<<endl;

        }

        printf("%d\n", MIN);

    }

    return ;

}

码农公寓

相关文章