shortest_path_negative

関数 · 単一始点最短路 (shortest_path)

template <weighted_graph_type G, class T = graph_weight_t<G>>
std::vector<T> shortest_path_negative(const G &g, int s = 0, T inf = std::numeric_limits<T>::max(), T ninf = std::numeric_limits<T>::lowest());

概要

単一始点最短路（負辺ありはベルマンフォード法）

テンプレートパラメータ

計算量

• $O(VE)$

備考

• 負閉路から到達できる頂点の距離は ninf（既定で lowest()）になる。

関連項目

• dijkstra_priority_queue — shortest_path の既定ヒープ（std::priority_queue ベースの最小ヒープ）
• decrease_key_heap — decrease-key（update）を持つヒープか
• shortest_path — 単一始点最短路（実重み付きグラフはダイクストラ法）
• shortest_path_spfa — 単一始点最短路（負辺ありは SPFA）