Shortest Path Faster Algorithm
(graph/shortest_path_faster_algorithm.hpp)

• View this file on GitHub
• Last update: 2021-08-30 04:35:37+09:00
• Include: #include "graph/shortest_path_faster_algorithm.hpp"

Depends on

• utils/macros.hpp

Code

#pragma once
#include <cassert>
#include <climits>
#include <cstdint>
#include <deque>
#include <tuple>
#include <utility>
#include <vector>
#include "../utils/macros.hpp"

/**
 * @brief Shortest Path Faster Algorithm
 * @note the interface is same to one of Bellman Ford
 */
std::vector<int64_t> shortest_path_faster_algorithm(int root, std::vector<std::vector<std::pair<int, int64_t> > > const & g) {
    assert (not g.empty());
    int n = g.size();
    std::vector<int64_t> dist(n, INT64_MAX);
    std::deque<int> cur, nxt;
    std::vector<bool> pushed(n);
    dist[root] = 0;
    nxt.push_back(root);
    pushed[root] = true;

    REP (iteration, 2 * n - 2) {
        cur.swap(nxt);
        while (not cur.empty()) {
            int x = cur.front();
            cur.pop_front();
            pushed[x] = false;
            for (const auto & edge : g[x]) {
                int y; int64_t cost; std::tie(y, cost) = edge;
                if ((dist[x] == INT64_MIN ? INT64_MIN : dist[x] + cost) < dist[y]) {
                    dist[y] = (iteration >= n - 1 ? INT64_MIN : dist[x] + cost);
                    if (not pushed[y]) {
                        if (not nxt.empty() and dist[y] < dist[nxt.front()]) {
                            // Small Label First
                            nxt.push_front(y);
                        } else {
                            nxt.push_back(y);
                        }
                        pushed[y] = true;
                    }
                }
            }
        }
        if (nxt.empty()) break;
    }

    return dist;
}

#line 2 "graph/shortest_path_faster_algorithm.hpp"
#include <cassert>
#include <climits>
#include <cstdint>
#include <deque>
#include <tuple>
#include <utility>
#include <vector>
#line 2 "utils/macros.hpp"
#define REP(i, n) for (int i = 0; (i) < (int)(n); ++ (i))
#define REP3(i, m, n) for (int i = (m); (i) < (int)(n); ++ (i))
#define REP_R(i, n) for (int i = (int)(n) - 1; (i) >= 0; -- (i))
#define REP3R(i, m, n) for (int i = (int)(n) - 1; (i) >= (int)(m); -- (i))
#define ALL(x) std::begin(x), std::end(x)
#line 10 "graph/shortest_path_faster_algorithm.hpp"

/**
 * @brief Shortest Path Faster Algorithm
 * @note the interface is same to one of Bellman Ford
 */
std::vector<int64_t> shortest_path_faster_algorithm(int root, std::vector<std::vector<std::pair<int, int64_t> > > const & g) {
    assert (not g.empty());
    int n = g.size();
    std::vector<int64_t> dist(n, INT64_MAX);
    std::deque<int> cur, nxt;
    std::vector<bool> pushed(n);
    dist[root] = 0;
    nxt.push_back(root);
    pushed[root] = true;

    REP (iteration, 2 * n - 2) {
        cur.swap(nxt);
        while (not cur.empty()) {
            int x = cur.front();
            cur.pop_front();
            pushed[x] = false;
            for (const auto & edge : g[x]) {
                int y; int64_t cost; std::tie(y, cost) = edge;
                if ((dist[x] == INT64_MIN ? INT64_MIN : dist[x] + cost) < dist[y]) {
                    dist[y] = (iteration >= n - 1 ? INT64_MIN : dist[x] + cost);
                    if (not pushed[y]) {
                        if (not nxt.empty() and dist[y] < dist[nxt.front()]) {
                            // Small Label First
                            nxt.push_front(y);
                        } else {
                            nxt.push_back(y);
                        }
                        pushed[y] = true;
                    }
                }
            }
        }
        if (nxt.empty()) break;
    }

    return dist;
}

Back to top page