[算法学习]Bellman-Ford算法求最短路

2021-02-17 06:18

阅读：413

标签：queue -- push turn org 就是 tor bsp 队列

OAO dijkstra算法在复杂度方面是十分优秀的，但是其最大弊端就是无法处理带负权的图

（因为是基于已经被更新过的距离源点的边必然已经达到了最短路的这个事实来采取贪心策略来求得最短路

而有负权路存在时，这个基础不在成立。）

这个时候就要请出Bellman-Ford算法了

(正确性证明：https://oi-wiki.org/graph/shortest-path/）

贴个代码emm：

#includeusing namespace std;

//Bellman-Ford 队列优化
const int maxn = 1e5 + 5;

struct edge{
    int to,w;
};

bool book[maxn];
int dis[maxn];
queueint> q;
vector edges[maxn];
int n,m,s;
int u,v,w;

int main(){
    cin>>n>>m>>s;
    while(m--){
        scanf("%d%d%d", &u, &v, &w);
        edges[u].push_back(edge{v,w});
    }
    fill(dis,dis+n+1,0x3f3f3f3f);
    dis[s] = 0;

    book[s] = 1;
    q.push(s);
    while(!q.empty()){
        int t = q.front();
        
        q.pop();
        for(int i = 0; i ){
            if(dis[edges[t][i].to] > dis[t] + edges[t][i].w){
                dis[edges[t][i].to] = dis[t] + edges[t][i].w;
                if(!book[edges[t][i].to]){
                    book[edges[t][i].to] = 1;
                    q.push(edges[t][i].to);
                }
            }
        }
        book[t] = 0;
    }

    for(int i = 1; i )
        cout" ";
    return 0;
}

对每个队列中的点，对所有的出边所对应的终点到源点的距离进行更新

再将被更新路径的点放入队列

直至没有点可以被放入队列（即所有点到源点的距离都最近）

然后Bellman-Ford的队列优化（也就是SPFA）是一种不稳定的优化，最差还是会退化至Bellman-Ford的O(NM)的

（emm也就是说特别构造的数据可以把SPFA卡到T掉，所以没有负权的话还是打dijkstra比较好）

[算法学习]Bellman-Ford算法求最短路

标签：queue -- push turn org 就是 tor bsp 队列

原文地址：https://www.cnblogs.com/leafsblogowo/p/12700316.html

上一篇：Leetcode哈希表算法

下一篇：spring5源码如何导入eclipse

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：[算法学习]Bellman-Ford算法求最短路
文章链接：http://soscw.com/index.php/essay/56445.html

亲，登录后才可以留言！

[算法学习]Bellman-Ford算法求最短路

评论

热门文章

推荐文章

最新文章

置顶文章