Bellman-Ford------解决负权边

2015年2月27日 2点热度 0条评论 来源: wikioi_bai

这几天一直在搞最短路专题,快开学了,希望能搞定这块和并查集,开学就弄数据结构和数学了。

其实Bellman-Ford算法是在于解决Dijkstra算法算不能解决的带有负权边的情况下产生的,其实Bellman-Ford算法相当的简单,核心代码只有4行的样子,但是真正理解这4行代码其实也是不难的。。。。

for ( int k = 1;k <= n-1;k++ )
{
	for ( int i = 1;i <= m;i++ )
	{
		if( dis[v[i]] > dis[u[i]]+w[i] )
		{
			dis[v[i]] = dis[u[i]]+w[i];
		}
	}
}

这简单的四行代码分别是什么意思呢,其实不难,先看第一个循环吧,说的就是k: 1->n-1,总共进行了n-1次的循环,第二层循环是对于每一条边,分别枚举各个情况下的松弛操作,说白了,就是对于这个图中的所有边进行最多n-1次松弛操作。

u[i] , v[i] , w[i] 分别表示什么呢?表示的是以u[i]为起点,v[i]为终点的,权值为w[i]的一条边了。

当然认真想想这个松弛操作也是不难的。。。我们只需要知道u[i]是起点,v[i]是终点,然后从源点到达终点的边可以和另外两条边构成一个三角形,这样的话,我们就可以得到了这个松弛的关系了。。。好了,其实Bellman-Ford算法就是这么简单,关于这个算法的应用,其实,他不仅仅是用来求最短路径的,还可以判断一个图中是否存在负权回路,要想知道一个图中是不是存在负权的回路,我们知道,在对于每一条边进行松弛操作的过程中,dis[ ]这个数组的值会在第k次松弛的操作后而保持不变( 1<=k<=n-1),关于他的上限为什么会是n-1的证明,我们会在后面继续讲到。如果在进行完n-1次操作后,dis[ ]的数组中的元素的值还是依旧在发生变化,那么我们就可以认为这个图中存在了负权的回路了,因为你想啊,如果有一个图中有负权的回路,那么这个图就不可能存在最短路,因为我每次都都在个圈,走上1000,,000次,值会原来越小。

关于他的上限为n-1次,其实也不难理解,如果一个图中有n个顶点的话,那么如果不存在回路,至多只能有n-1条边,有了这个概念,我们刚刚已经分析了,要想存在最短路,是不能有负权回路的,这个时候,我们来分析下,又不有可能存在一个正权回路,答案当然也是不可能的,因为如果存在正权回路的话,最短路一定不会包括它,因为如果走进了这个圈,权值会越加越大。。。。

好了,这些就是关于Bellman-Ford算法的一些简单的介绍,,有了这些介绍,我们在学习SPFA的过程中就会打下良好的基础了,,,

代码:

# include<cstdio>
# include<iostream>

using namespace std;

# define inf 99999999

int u[10];
int v[10];
int w[10];
int dis[10];
int n,m;

void input()
{
    for ( int i = 1;i <= m;i++ )
    {
        cin>>u[i]>>v[i]>>w[i];
    }
}

void init()
{
    for ( int i = 1;i <= n;i++ )
    {
        dis[i] = inf;
    }
    dis[1] = 0;
}

void solve()
{
    int check;
    for ( int k = 1;k <= n-1;k++ )
    {
        for ( int i = 1;i <= m;i++ )
        {
            check = 0;
            if ( dis[v[i]] > dis[u[i]] + w[i] )
            {
                dis[v[i]] = dis[u[i]] + w[i];
                check = 1;
            }

        }
        if ( check == 0 )
            break;
    }

}

void output()
{
    int flag = 0;
    for ( int i = 1;i <= m;i++ )
    {
        if ( dis[v[i]] > dis[u[i]]+w[i] )
        {
            flag = 1;
        }
    }
    if ( flag == 1 )
    {
        cout<<"此图含有负权回路"<<endl;
    }
    else
    {
        for ( int i = 1;i <= n;i++ )
        {
            cout<<dis[i]<<" ";
        }
    }
}


int main(void)
{
    while ( cin>>n>>m )
    {
        input();
        init();
        solve();
        output();
    }


    return 0;
}

    原文作者:wikioi_bai
    原文地址: https://blog.csdn.net/wikioi_bai/article/details/43973115
    本文转自网络文章,转载此文章仅为分享知识,如有侵权,请联系管理员进行删除。