wf (ワーシャルフロイド simple ver)
(src/graph/simple/wf.hpp)

• View this file on GitHub
• Last update: 2022-12-07 03:13:59+09:00
• Include: #include "src/graph/simple/wf.hpp"

概要

辺重み付きグラフ $G(V, E)$ の全対間最短経路を計算します。

機能

std::vector<std::vector<cost_type>> wf<cost_type>(const std::vector<std::vector<std::pair<int, cost_type>>>& G, cost_type inf = std::numeric_limits<cost_type>::max() / 3)

• cost_type: 辺の重みの型(テンプレート引数)
  • int、long、long long以外での使用を想定していません。
• G: グラフの隣接リストを表す二次元vector
  • uからvへのコストwの有向辺 $(u, v, w) \in E$ について、G[u]にstd::pair(v, w)が存在するようにしてください
  • AtCoder等では、zawa::read_weighted_graphを用いて標準入力から対応するGを生成できます。
• inf: テーブル更新の初期値
  • デフォルトでstd::numeric_limits<cost_type>::max() / 3が定められていますが、自分で指定することを強く推奨します。
• 返り値: 全対間最短経路を表す二次元vector
  • res[i][j]に頂点iから頂点jへの最短経路の総コストが入ります。
  • 頂点iから頂点jに到達できない時に、res[i][j] == infとは限らないことに注意してください(チェックの仕方は例えばtest/simple-wf1.test.cppを確認してください)
• 計算量: $O(\mid V \mid^3)$
  • $O(\mid V \mid^3\ +\ \mid E \mid)$ なのかなと思ったけど、そもそも $\mid E\mid < \mid V \mid^2$ なので….
    • 多重辺？知らない子ですね….

Verified with

• test/simple-wf1.test.cpp

Code

#pragma once

#include <vector>
#include <utility>
#include <limits>
#include <algorithm>

namespace zawa {

template <class cost_type>
std::vector<std::vector<cost_type>> wf(const std::vector<std::vector<std::pair<int, cost_type>>>& G, cost_type inf = std::numeric_limits<cost_type>::max() / 3) {
    std::vector res(G.size(), std::vector(G.size(), inf));
    for (std::size_t i = 0 ; i < G.size() ; i++) {
        res[i][i] = 0;
    }
    for (std::size_t i = 0 ; i < G.size() ; i++) {
        for (auto [x, w] : G[i]) {
            res[i][x] = std::min(res[i][x], w);
        }
    }
    for (std::size_t k = 0 ; k < G.size() ; k++) {
        for (std::size_t i = 0 ; i < G.size() ; i++) {
            for (std::size_t j = 0 ; j < G.size() ; j++) {
                res[i][j] = std::min(res[i][j], res[i][k] + res[k][j]);
            }
        }
    }
    return res;
}

} // namespace zawa

#line 2 "src/graph/simple/wf.hpp"

#include <vector>
#include <utility>
#include <limits>
#include <algorithm>

namespace zawa {

template <class cost_type>
std::vector<std::vector<cost_type>> wf(const std::vector<std::vector<std::pair<int, cost_type>>>& G, cost_type inf = std::numeric_limits<cost_type>::max() / 3) {
    std::vector res(G.size(), std::vector(G.size(), inf));
    for (std::size_t i = 0 ; i < G.size() ; i++) {
        res[i][i] = 0;
    }
    for (std::size_t i = 0 ; i < G.size() ; i++) {
        for (auto [x, w] : G[i]) {
            res[i][x] = std::min(res[i][x], w);
        }
    }
    for (std::size_t k = 0 ; k < G.size() ; k++) {
        for (std::size_t i = 0 ; i < G.size() ; i++) {
            for (std::size_t j = 0 ; j < G.size() ; j++) {
                res[i][j] = std::min(res[i][j], res[i][k] + res[k][j]);
            }
        }
    }
    return res;
}

} // namespace zawa

Back to top page