最短路径之bellman—ford

2018年8月24日 2点热度 0条评论 来源: qq_42370259

bellman-ford's algorithm复杂度为O()比Dijkstra's algorithm 慢,但其可用于计算有负权边时的最短路

主要就是三个部分:

1.初始化所有的dis[ v ]=INF,dis[ v ]为v点到源点的距离,并令dia[start]=0,源点的距离为0;

2.对于每条边进行n-1次松弛操作; dis[v]=min(dis[v],dis[u]+w);该操作即为松弛,关于松弛的概念我不是很懂,我认为就是不断的接近正确的值。(如有错误,欢迎指正)。

3.第二步执行完之后,所有边应该无法再松弛,如果还可以就说明有负环,否则无负环。

代码如下:

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

static const int maxn=100;//点的数目
static const int INF=0x3f3f3f3f;

int dis[maxn];
struct edge{
    int u;
    int v;
    int w;
}e;
vector<edge>E;
bool bellman_ford(int start,int n)//源点start,n个点
{
    memset(dis,INF,sizeof(dis));
    dis[start]=0;
    for(int i=0;i<n-1;i++)
    {
        for(int j=0;j<E.size();j++)
        {
            int u=E[j].u;
            int v=E[j].v;
            int w=E[j].w;
            dis[v]=min(dis[v],dis[u]+w);
        }
    }
    for(int i=0;i<E.size();i++)
    {
        if(dis[E[i].v]>dis[E[i].u]+E[i].w)
        return false;//有负环,不存在最短路
    }
    return true;//无负环,存在最短路
}
int main()
{
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        int u,k;
        cin>>u>>k;
        while(k--)
        {
            int v,w;
            cin>>v>>w;
            e.u=u;e.v=v;e.w=w;
            E.push_back(e);
        }
    }
    cout<<"*****************"<<endl;//输出
    if(bellman_ford(0,n))
    {
        for(int i=0;i<n;i++)
        cout<<i<<" "<<dis[i]<<endl;
    }
    return 0;
}

 

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