Bellmm-ford算法

解决什么样的问题

有边数限制的最短路，存在负权边，负环

概念

通俗的来讲就是：假设 1 号点到 n 号点是可达的，每一个点同时向指向的方向出发，更新相邻的点的最短距离，通过循环 n-1 次操作，若图中不存在负环，则 1 号点一定会到达 n 号点，若图中存在负环，则在 n-1 次松弛后一定还会更新

思路

for k次
　　for 所有边 a,b,w (松弛操作)
　　　　dist[b] = min(dist[b],back[a] + w)

注意：back[] 数组是上一次迭代后 dist[] 数组的备份，由于是每个点同时向外出发，因此需要对 dist[] 数组进行备份，若不进行备份会因此发生串联效应，影响到下一个点

①初始化距离数组，其他为无穷，起点距离为0

②外层for循环k次，代表最多走k次，内层循环所有边，更新最短距离，整体复杂度为O（n*m）

具体算法实现上，在内层循环开始前，加一个last数组，来存储上一次dist数组的距离，防止串联

注意：是否能到达n号点的判断中需要进行if(dist[n] > INF/2)判断，而并非是if(dist[n] == INF)判断，原因是INF是一个确定的值，并非真正的无穷大，会随着其他数值而受到影响，dist[n]大于某个与INF相同数量级的数即可。

代码

题目：https://www.acwing.com/problem/content/855/

#include<bits/stdc++.h>

using namespace std;

const int N=550,M=10010;

struct Edge

{

    int a, b, c;

}edges[M];

int n,m,k;

int dist[N];

int last[N];

int bellmm_ford()

{

    memset(dist,0x3f,sizeof(dist));

    dist[1]=0;

    for(int i=0;i<k;i++)

    {

        //加入last数组，是为了防止进行串联

        //保存上一次的dist数组距离

        memcpy(last,dist,sizeof(last));

        for(int j=0;j<m;j++)

        {

            auto e=edges[j];

            dist[e.b]=min(dist[e.b],last[e.a]+e.c);

        }

    }

    //因为他是存在负边的，会有某个点到最终点权值为负，则会更新最终点的距离，使它小于0x3f3f3f3f,故由此判断

    if(dist[n]<0x3f3f3f3f/2)

        return dist[n];

    else

        return -1;

}

int main()

{

    int i,j;

    cin>>n>>m>>k;

    for(i=0;i<m;i++)

    {

        int a,b,c;

        cin>>a>>b>>c;

        edges[i]={a,b,c};

    }

    int ans=bellmm_ford();

    if(ans!=-1)

        cout<<ans;

    else

        cout<<"impossible";

    return 0;

}

巴特西

最短路-Bellmm-ford算法

Bellmm-ford算法

解决什么样的问题

概念

思路

代码

最新文章

热门文章