cplib/graph/dijkstra.hpp

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

Depends on

• cplib/graph/graph.hpp

Code

#ifndef CPLIB_DIJKSTRA_HPP
#define CPLIB_DIJKSTRA_HPP

#include "cplib/graph/graph.hpp"
#include <algorithm>
#include <cmath>
#include <limits>
#include <set>
#include <utility>
#include <vector>

namespace cplib
{
using namespace std;

template <typename W, W INF = numeric_limits<W>::max()>
struct Dijkstra
{
    Graph<W> const &g;
    int             src;
    vector<int>     p;
    vector<W>       d;

    Dijkstra(Graph<W> const &g) : g(g), p(g.size()), d(g.size()){};
    void run(int src = 0)
    {
        this->src = src;
        fill(begin(p), end(p), -1);
        fill(begin(d), end(d), INF);

        set<pair<W, int>> q;
        d[src] = 0;
        q.emplace(d[src], src);
        while (!q.empty())
        {
            int u = q.begin()->second;
            q.erase(q.begin());

            for (auto [v, w] : g[u])
            {
                if (d[u] + w < d[v])
                {
                    q.erase({d[v], v});
                    d[v] = d[u] + w;
                    p[v] = u;
                    q.emplace(d[v], v);
                }
            }
        }
    }

    void run_avoid(int src, int prohibited)
    {
        this->src = src;
        fill(begin(p), end(p), -1);
        fill(begin(d), end(d), INF);

        set<pair<W, int>> q;
        d[src] = 0;
        q.emplace(d[src], src);
        while (!q.empty())
        {
            int u = q.begin()->second;
            q.erase(q.begin());

            for (auto [v, w] : g[u])
            {
                if (v == prohibited)
                    continue;
                if (d[u] + w < d[v])
                {
                    q.erase({d[v], v});
                    d[v] = d[u] + w;
                    p[v] = u;
                    q.emplace(d[v], v);
                }
            }
        }
    }

    Graph<W> shortest_path_DAG(void) const
    {
        int      n = g.size();
        Graph<W> dag(n);
        for (int v = 0; v < n; ++v)
            if (auto u = p[v]; u != -1)
                dag.add_edge(u, v, d[v] - d[u]);
        return dag;
    }

    vector<int> shortest_path(int u) const
    {
        if (d[u] == INF)
            return {};
        vector<int> path;

        for (int v = u; v != src; v = p[v])
            path.push_back(v);
        path.push_back(src);

        reverse(begin(path), end(path));
        return path;
    }
    bool is_reachable(int u) { return d[u] != INF; }
    W    distance(int u) { return d[u]; }
    void operator()(int src = 0) { run(src); }
};
} // namespace cplib

#endif // CPLIB_DIJKSTRA_HPP

#line 1 "cplib/graph/dijkstra.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 6 "cplib/graph/dijkstra.hpp"
#include <cmath>
#include <limits>
#include <set>
#line 11 "cplib/graph/dijkstra.hpp"

namespace cplib
{
using namespace std;

template <typename W, W INF = numeric_limits<W>::max()>
struct Dijkstra
{
    Graph<W> const &g;
    int             src;
    vector<int>     p;
    vector<W>       d;

    Dijkstra(Graph<W> const &g) : g(g), p(g.size()), d(g.size()){};
    void run(int src = 0)
    {
        this->src = src;
        fill(begin(p), end(p), -1);
        fill(begin(d), end(d), INF);

        set<pair<W, int>> q;
        d[src] = 0;
        q.emplace(d[src], src);
        while (!q.empty())
        {
            int u = q.begin()->second;
            q.erase(q.begin());

            for (auto [v, w] : g[u])
            {
                if (d[u] + w < d[v])
                {
                    q.erase({d[v], v});
                    d[v] = d[u] + w;
                    p[v] = u;
                    q.emplace(d[v], v);
                }
            }
        }
    }

    void run_avoid(int src, int prohibited)
    {
        this->src = src;
        fill(begin(p), end(p), -1);
        fill(begin(d), end(d), INF);

        set<pair<W, int>> q;
        d[src] = 0;
        q.emplace(d[src], src);
        while (!q.empty())
        {
            int u = q.begin()->second;
            q.erase(q.begin());

            for (auto [v, w] : g[u])
            {
                if (v == prohibited)
                    continue;
                if (d[u] + w < d[v])
                {
                    q.erase({d[v], v});
                    d[v] = d[u] + w;
                    p[v] = u;
                    q.emplace(d[v], v);
                }
            }
        }
    }

    Graph<W> shortest_path_DAG(void) const
    {
        int      n = g.size();
        Graph<W> dag(n);
        for (int v = 0; v < n; ++v)
            if (auto u = p[v]; u != -1)
                dag.add_edge(u, v, d[v] - d[u]);
        return dag;
    }

    vector<int> shortest_path(int u) const
    {
        if (d[u] == INF)
            return {};
        vector<int> path;

        for (int v = u; v != src; v = p[v])
            path.push_back(v);
        path.push_back(src);

        reverse(begin(path), end(path));
        return path;
    }
    bool is_reachable(int u) { return d[u] != INF; }
    W    distance(int u) { return d[u]; }
    void operator()(int src = 0) { run(src); }
};
} // namespace cplib

Back to top page