重みあり単一始点最短経路 (Single Source Shortest Path in Unweighted Graph, SPFA)
(src/graph/single-source-shortest-path/in-weighted-graph.hpp)
Appendix
単一始点最短経路問題の solver の細かい仕様について
テンプレートパラメータに渡すグラフ $G$ の仕様について
コンストラクタ
sssp::InWeightedGraph(const G &g, usize s)
頂点 $s$ からの重みあり単一始点最短経路問題を解く。
コンストラクタ内部では以下が行われている。
- 始点から各頂点への最短経路のコストの計算
- 以下で特定される最短経路木を一つ構成
計算量
get_original_graph
G get_original_graph() const
もとのグラフを返す。
inf
$s$ からの経路が存在しないような頂点 $v$ への $s$ からの最短経路のコストとして定義されている値を返す。
内部では std::numeric_limits< cost_type >::max()
によって定義されている。
negative_inf
static cost_type negative_inf()
$s$ から $v$ への経路に負閉路が含まれる場合の最短経路のコストとして定義されている値を返す。
内部では std::numeric_limits< cost_type >::min()
によって定義されている。
distance
cost_type distance(const usize v) const
$s$ から $v$ への最短経路のコストを返す。経路が存在しない場合のコストは inf()
として定義されている。
get_distances
std::vector< cost_type > get_distances() const
各頂点に対する distance
を std::vector
で wrap して返す。distance(v)
は v
番目の要素として表される。
$s$ からの経路が存在しないような頂点へのコストは inf()
として定義されている。
undefined
構成された最短経路木において親が存在しない、または経路上に負閉路が含まれるときに返される値。
内部では std::numeric_limits< usize >::max()
によって定義されている。
parent
usize parent(const usize v) const
構成された最短経路木においての v
の親を返す。
親が存在しない、または経路上に負閉路が含まれる場合 undefined()
が返される。
get_parents
std::vector< usize > get_parents() const
各頂点に対する parent
を std::vector
で wrap して返す。parent(v)
は v
番目の要素として表される。
親が存在しない、または経路上に負閉路が含まれる頂点に対応する要素は undefined()
となる。
edge_label
usize edge_label(const usize v) const
構成された最短経路木における v
とその親との間にある辺の、もとのグラフでの辺番号を返す。
親が存在しない、または経路上に負閉路が含まれる場合 undefined()
が返される。
get_edge_labels
usize get_edge_labels() const
各頂点に対する edge_label(v)
を std::vector
で wrap して返す。edge_label(v)
は v
番目の要素として表される。
親が存在しない、または経路上に負閉路が含まれる頂点に対応する要素は undefined()
となる。
Depends on
Verified with
Code
Back to top page