cpp_src/graph/ShortestPath.hpp

• View this file on GitHub
• Last update: 2022-09-03 23:41:09+09:00
• Include: #include "cpp_src/graph/ShortestPath.hpp"

Code

// ABC264G
template <class T>
V<T> bellman_ford(const Graph<T>& g, int s = 0) {
    const auto INF = numeric_limits<T>::max();
    int n = g.size();

    V<T> ds(n, INF);
    ds[s] = 0;

    rep(i, n) {
        rep(v, n) {
            for (auto& e : g[v]) {
                if (ds[e.from] == INF) continue;
                chmin(ds[e.to], ds[e.from] + e.cost);
            }
        }
    }

    rep(v, n) {
        for (auto& e : g[v]) {
            if (ds[e.from] == INF) continue;
            if (ds[e.from] + e.cost < ds[e.to]) return V<T>();
        }
    }
    return ds;
}

// cost = 1 or tree
template <class T>
V<T> bfs(const Graph<T>& g, int s = 0) {
    const T inf = numeric_limits<T>::max() / 2;
    int n = g.size();

    V<T> ds(n, inf);
    queue<int> que;
    que.push(s);
    ds[s] = 0;

    while (!que.empty()) {
        auto v = que.front();
        que.pop();
        for (auto e : g[v]) {
            T nx = ds[v] + e.cost;
            if (ds[e.to] > nx) {
                ds[e.to] = nx;
                que.push(e.to);
            }
        }
    }
    for (auto& x : ds)
        if (x == inf) x = -1;
    return ds;
}

// must be optimized
template <class T>
V<T> bfs01(const Graph<T>& g, int s = 0) {
    const T inf = numeric_limits<T>::max() / 2;
    int n = g.size();

    V<T> ds(n, inf);
    using P = pair<T, int>;
    deque<int> que;
    que.push_back(s);
    ds[s] = 0;

    while (!que.empty()) {
        auto v = que.front();
        que.pop_front();
        for (auto e : g[v]) {
            T nx = ds[v] + e.cost;
            if (ds[e.to] > nx) {
                ds[e.to] = nx;
                if (e.cost == 0) {
                    que.push_front(e.to);
                } else {
                    que.push_back(e.to);
                }
            }
        }
    }
    for (auto& x : ds)
        if (x == inf) x = -1;
    return ds;
}

template <class T>
V<T> dijkstra(const Graph<T>& g, int s = 0) {
    const T inf = numeric_limits<T>::max() / 2;
    int n = g.size();

    V<T> ds(n, inf);
    using P = pair<T, int>;
    priority_queue<P, V<P>, greater<P>> que;
    que.emplace(0, s);
    ds[s] = 0;
    while (!que.empty()) {
        auto p = que.top();
        que.pop();
        int v = p.se;
        if (ds[v] < p.fi) continue;
        for (auto e : g[v]) {
            T nx = ds[v] + e.cost;
            if (ds[e.to] > nx) {
                ds[e.to] = nx;
                que.emplace(nx, e.to);
            }
        }
    }
    for (auto& x : ds)
        if (x == inf) x = -1;
    return ds;
}

#line 1 "cpp_src/graph/ShortestPath.hpp"
// ABC264G
template <class T>
V<T> bellman_ford(const Graph<T>& g, int s = 0) {
    const auto INF = numeric_limits<T>::max();
    int n = g.size();

    V<T> ds(n, INF);
    ds[s] = 0;

    rep(i, n) {
        rep(v, n) {
            for (auto& e : g[v]) {
                if (ds[e.from] == INF) continue;
                chmin(ds[e.to], ds[e.from] + e.cost);
            }
        }
    }

    rep(v, n) {
        for (auto& e : g[v]) {
            if (ds[e.from] == INF) continue;
            if (ds[e.from] + e.cost < ds[e.to]) return V<T>();
        }
    }
    return ds;
}

// cost = 1 or tree
template <class T>
V<T> bfs(const Graph<T>& g, int s = 0) {
    const T inf = numeric_limits<T>::max() / 2;
    int n = g.size();

    V<T> ds(n, inf);
    queue<int> que;
    que.push(s);
    ds[s] = 0;

    while (!que.empty()) {
        auto v = que.front();
        que.pop();
        for (auto e : g[v]) {
            T nx = ds[v] + e.cost;
            if (ds[e.to] > nx) {
                ds[e.to] = nx;
                que.push(e.to);
            }
        }
    }
    for (auto& x : ds)
        if (x == inf) x = -1;
    return ds;
}

// must be optimized
template <class T>
V<T> bfs01(const Graph<T>& g, int s = 0) {
    const T inf = numeric_limits<T>::max() / 2;
    int n = g.size();

    V<T> ds(n, inf);
    using P = pair<T, int>;
    deque<int> que;
    que.push_back(s);
    ds[s] = 0;

    while (!que.empty()) {
        auto v = que.front();
        que.pop_front();
        for (auto e : g[v]) {
            T nx = ds[v] + e.cost;
            if (ds[e.to] > nx) {
                ds[e.to] = nx;
                if (e.cost == 0) {
                    que.push_front(e.to);
                } else {
                    que.push_back(e.to);
                }
            }
        }
    }
    for (auto& x : ds)
        if (x == inf) x = -1;
    return ds;
}

template <class T>
V<T> dijkstra(const Graph<T>& g, int s = 0) {
    const T inf = numeric_limits<T>::max() / 2;
    int n = g.size();

    V<T> ds(n, inf);
    using P = pair<T, int>;
    priority_queue<P, V<P>, greater<P>> que;
    que.emplace(0, s);
    ds[s] = 0;
    while (!que.empty()) {
        auto p = que.top();
        que.pop();
        int v = p.se;
        if (ds[v] < p.fi) continue;
        for (auto e : g[v]) {
            T nx = ds[v] + e.cost;
            if (ds[e.to] > nx) {
                ds[e.to] = nx;
                que.emplace(nx, e.to);
            }
        }
    }
    for (auto& x : ds)
        if (x == inf) x = -1;
    return ds;
}

Back to top page