01-BFS
(graph/shortestpath/01_bfs.hpp)

• View this file on GitHub
• Last update: 2020-08-25 17:20:34+09:00
• Include: #include "graph/shortestpath/01_bfs.hpp"

概要

単一始点最短路. 辺の重みが$0$または$1$のみである必要がある.

計算量

$O(E + V)$

使用例

• bfs_01(g, frm) : frmから01-BFS.
  • 返り値の型 : vector<T>

Verified with

• test/aoj/2945.test.cpp

Code

/**
* @brief 01-BFS
* @docs docs/graph/shortestpath/01_bfs.md
*/

template <typename T>
vector<T> bfs_01(const Graph<T>& g, int frm) {
    vector<T> ret(g.V, GINF<T>);
    ret[frm] = 0;
    deque<int> dq;
    dq.emplace_back(frm);
    while (not dq.empty()) {
        int idx = dq.front();
        dq.pop_front();
        for (auto& e : g.mat[idx]) {
            T nxt_cst = ret[idx] + e.cst;
            if (ret[e.to] <= nxt_cst) continue;
            ret[e.to] = nxt_cst;
            if (e.cst == 0) dq.emplace_front(e.to);
            else
                dq.emplace_back(e.to);
        }
    }
    return ret;
}

#line 1 "graph/shortestpath/01_bfs.hpp"
/**
* @brief 01-BFS
* @docs docs/graph/shortestpath/01_bfs.md
*/

template <typename T>
vector<T> bfs_01(const Graph<T>& g, int frm) {
    vector<T> ret(g.V, GINF<T>);
    ret[frm] = 0;
    deque<int> dq;
    dq.emplace_back(frm);
    while (not dq.empty()) {
        int idx = dq.front();
        dq.pop_front();
        for (auto& e : g.mat[idx]) {
            T nxt_cst = ret[idx] + e.cst;
            if (ret[e.to] <= nxt_cst) continue;
            ret[e.to] = nxt_cst;
            if (e.cst == 0) dq.emplace_front(e.to);
            else
                dq.emplace_back(e.to);
        }
    }
    return ret;
}

Back to top page