graph/bellman-ford.cpp

Back to top page

• category: graph
• View this file on GitHub
  • Last commit date: 2020-06-15 15:40:57+09:00

Verified with

• test/bellman-ford.test.cpp

Code

template <typename T>
vector<T> bellman_ford(const Edges<T> &edges, int n, int s) {
    constexpr auto INF = numeric_limits<T>::max();
    vector<T> dist(n, INF);
    dist[s] = 0;
    rep(i, n - 1) {
        for (const auto &e : edges) {
            if (dist[e.from] == INF)
                continue;
            dist[e.to] = min(dist[e.to], dist[e.from] + e.cost);
        }
    }

    for (const auto &e : edges) {
        if (dist[e.from] == INF)
            continue;
        if (dist[e.from] + e.cost < dist[e.to])
            return vector<T>();
    }
    return dist;
}

#line 1 "graph/bellman-ford.cpp"
template <typename T>
vector<T> bellman_ford(const Edges<T> &edges, int n, int s) {
    constexpr auto INF = numeric_limits<T>::max();
    vector<T> dist(n, INF);
    dist[s] = 0;
    rep(i, n - 1) {
        for (const auto &e : edges) {
            if (dist[e.from] == INF)
                continue;
            dist[e.to] = min(dist[e.to], dist[e.from] + e.cost);
        }
    }

    for (const auto &e : edges) {
        if (dist[e.from] == INF)
            continue;
        if (dist[e.from] + e.cost < dist[e.to])
            return vector<T>();
    }
    return dist;
}

Back to top page