首页 > 编程语言 > 详细

spfa 算法模板 可求带负权边的最短路

时间:2018-02-14 23:32:05      阅读:231      评论:0      收藏:0      [点我收藏+]

标签:cto   nbsp   init   ems   push   name   for   如果   class   

  它是队列优化的Bellman-Ford算法。

  优化的原理是:下一次松弛操作时被更新dis的点其实与上一次被更新的点有关!如果上一次被更新的点有一条边指向某点V,那么在下一次,点V就是可能被更新dis的点。

  和 Bellman-Ford 算法一样,它可以用来求带负权边的最短路,如果存在一个从源点可以到达的权重为负值的环路,则返回false表示无解决方案,因为可以不断在这个环路中循环使总代价越来越小;如果不存在则返回true。

  

#include<iostream>
#include<algorithm>
#include<cstring>
#include<string>
#include<set>
#include<queue>
using namespace std;
#define INF 0x3f3f3f3f
#define M(a, b) memset(a, b, sizeof(a))
const int maxn = 1000 + 5;

struct Edge {
    int from, to, dist;
};

struct SPFA {
    int d[maxn], cnt[maxn], p[maxn];
    int n, m;
    bool inq[maxn];
    vector<int> G[maxn];
    vector<Edge> edges;

    void init(int n) {
        this->n = n;
        for (int i = 1; i <= n; ++i) G[i].clear();
        edges.clear();
    }

    void AddEdge(int from, int to, int dist) {
        edges.push_back(Edge{from, to, dist});
        int m = edges.size();
        G[from].push_back(m-1);
    }

    bool spfa(int s) {
        M(d, INF); M(cnt, 0); M(inq, 0);
        d[s] = 0;
        queue<int> q;
        q.push(s);
        inq[s] = true;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            inq[u] = false;
            for (int i = 0; i < G[u].size(); ++i) {
                Edge &e = edges[G[u][i]];
                if (d[e.to] > d[u] + e.dist) {
                    d[e.to] = d[u] + e.dist;
                    p[e.to] = G[u][i];
                    if (!inq[e.to]) {
                        q.push(e.to); inq[e.to] = true; 
                        if (++cnt[e.to] > n) return false;
                    }
                }
            }
        }
        return true;
    }

};

SPFA solver;

int main() {
    int n, m, a, b, c;
    while(cin >> m >> n) {
        solver.init(n);
        while(m--) {
            cin >> a >> b >> c;
            solver.AddEdge(a, b, c);
            solver.AddEdge(b, a, c);
        }
        solver.spfa(1);
        cout << solver.d[n] << endl;
    }
    return 0;
}

 

spfa 算法模板 可求带负权边的最短路

标签:cto   nbsp   init   ems   push   name   for   如果   class   

原文:https://www.cnblogs.com/Bw98blogs/p/8449076.html

(0)
(0)
   
举报
评论 一句话评论(0
0条  
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号