shortest_path_spfa
template <weighted_graph_type G, class T = graph_weight_t<G>>
std::vector<T> shortest_path_spfa(const G &g, int s = 0, T inf = std::numeric_limits<T>::max());
概要
単一始点最短路（負辺ありは SPFA）
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
G |
重み付きグラフ型（list_graph<T> / csr_graph<T> のいずれでも可） |
計算量
- 平均 $O(E)$、最悪 $O(VE)$
備考
- 負閉路を検出した場合は空の
vectorを返す。
関連項目
dijkstra_priority_queue— shortest_path の既定ヒープ（std::priority_queue ベースの最小ヒープ）decrease_key_heap— decrease-key（update）を持つヒープかshortest_path— 単一始点最短路（実重み付きグラフはダイクストラ法）shortest_path_negative— 単一始点最短路（負辺ありはベルマンフォード法）