cplib/graph/spfa.hpp

• View this file on GitHub
• Last update: 2022-01-02 13:06:06-05:00
• Include: #include "cplib/graph/spfa.hpp"

Depends on

• cplib/graph/graph.hpp

Code

#ifndef CPLIB_SPFA_HPP
#define CPLIB_SPFA_HPP

#include "cplib/graph/graph.hpp"
#include <limits>
#include <queue>

namespace cplib
{
using namespace std;

template <typename W, W INF = numeric_limits<W>::max()>
struct SPFA
{
    Graph<W> const &g;
    vector<W>       dist;
    SPFA(Graph<W> const &g) : g(g) {}
    bool operator()(int s)
    {
        int n = g.size();
        dist.assign(n, INF);
        vector<int>  cnt(n, 0);
        vector<bool> inqueue(n, false);
        queue<int>   q;

        dist[s] = 0;
        q.push(s);
        inqueue[s] = true;
        while (!q.empty())
        {
            int v = q.front();
            q.pop();
            inqueue[v] = false;

            for (auto edge : g[v])
            {
                int to  = edge.first;
                int len = edge.second;

                if (dist[v] + len < dist[to])
                {
                    dist[to] = dist[v] + len;
                    if (!inqueue[to])
                    {
                        q.push(to);
                        inqueue[to] = true;
                        cnt[to]++;
                        if (cnt[to] > n)
                            return false; // negative cycle
                    }
                }
            }
        }
        return true;
    }
};
} // namespace cplib

#endif // CPLIB_SPFA_HPP

#line 1 "cplib/graph/spfa.hpp"



#line 1 "cplib/graph/graph.hpp"



#include <algorithm>
#include <cassert>
#include <utility>
#include <vector>

namespace cplib
{
using namespace std;

template <typename W>
struct Graph
{
    using adj_list = vector<pair<int, W>>;
    vector<adj_list> g;

    Graph(int n = 0) : g(n) {}

    size_t size() const { return g.size(); }
    int    vertex(pair<int, W> e) const { return e.first; }
    void   add_edge(int u, int v) { g[u].emplace_back(v, W()); }
    void   add_edge(int u, int v, W weights) { g[u].emplace_back(v, weights); }
    void   add_undirected_edge(int u, int v)
    {
        g[u].emplace_back(v, W());
        g[v].emplace_back(u, W());
    }
    void add_undirected_edge(int u, int v, W weights)
    {
        g[u].emplace_back(v, weights);
        g[v].emplace_back(u, weights);
    }
    int add_node(void)
    {
        g.push_back({});
        return g.size() - 1;
    }

    adj_list &operator[](int u) { return g[u]; }
    adj_list  operator[](int u) const { return g[u]; }

    typename vector<adj_list>::iterator begin() { return g.begin(); };
    typename vector<adj_list>::iterator end() { return g.end(); }

    typename vector<adj_list>::const_iterator begin() const
    {
        return g.begin();
    };
    typename vector<adj_list>::const_iterator end() const { return g.end(); }
};

template <>
struct Graph<void>
{
    using adj_list = vector<int>;
    vector<adj_list> g;

    Graph(int n = 0) : g(n) {}

    size_t size() const { return g.size(); }
    int    vertex(int e) const { return e; }
    void   add_edge(int u, int v) { g[u].emplace_back(v); }
    void   add_undirected_edge(int u, int v)
    {
        g[u].push_back(v);
        g[v].push_back(u);
    }
    int add_node(void)
    {
        g.push_back({});
        return g.size() - 1;
    }

    adj_list &operator[](int u) { return g[u]; }
    adj_list  operator[](int u) const { return g[u]; }

    typename vector<adj_list>::iterator begin() { return g.begin(); };
    typename vector<adj_list>::iterator end() { return g.end(); }

    typename vector<adj_list>::const_iterator begin() const
    {
        return g.begin();
    };
    typename vector<adj_list>::const_iterator end() const { return g.end(); }
};

using UndirectedGraph = Graph<void>;

} // namespace cplib


#line 5 "cplib/graph/spfa.hpp"
#include <limits>
#include <queue>

namespace cplib
{
using namespace std;

template <typename W, W INF = numeric_limits<W>::max()>
struct SPFA
{
    Graph<W> const &g;
    vector<W>       dist;
    SPFA(Graph<W> const &g) : g(g) {}
    bool operator()(int s)
    {
        int n = g.size();
        dist.assign(n, INF);
        vector<int>  cnt(n, 0);
        vector<bool> inqueue(n, false);
        queue<int>   q;

        dist[s] = 0;
        q.push(s);
        inqueue[s] = true;
        while (!q.empty())
        {
            int v = q.front();
            q.pop();
            inqueue[v] = false;

            for (auto edge : g[v])
            {
                int to  = edge.first;
                int len = edge.second;

                if (dist[v] + len < dist[to])
                {
                    dist[to] = dist[v] + len;
                    if (!inqueue[to])
                    {
                        q.push(to);
                        inqueue[to] = true;
                        cnt[to]++;
                        if (cnt[to] > n)
                            return false; // negative cycle
                    }
                }
            }
        }
        return true;
    }
};
} // namespace cplib

Back to top page