Shortest Path (単一始点最短路)
(graph/shortest_path.hpp)
単一始点最短路問題を解く.solve(int s, int t = INVALID)
関数を用いると以下の要領でアルゴリズムが自動的に選択される.
- 負の重みの辺が存在するならば,Bellman-Ford 法で解く.$O(VE)$
- 全ての辺重みが非負で,非零の辺重みの値が高々一通りならば, 0-1 BFS で解く.$O(V + E)$
- 全ての辺重みが非負で,辺重みの最大値 $w_{\max}$ が十分小さければ Dial 法で解く.$O(w_{\max} V + E)$
- それ以外の場合,Dijkstra 法で解く.$O(V^2 + E)$ または $O(E \log E)$
なお,頂点 $t$ までの最短路が見つかった場合その時点でソルバーは実行を停止する.また,SPFA ($O(VE)$),全点対最短路アルゴリズム(Floyd-Warshall 法,$O(E + V^3)$),DAG用ソルバー($O(V + E)$)も実装されている.retrieve_path(int t)
で最短路の復元が,また to_dot(string filename)
で .DOT
形式のグラフ出力が可能.
使用方法
constexpr long long INF = 1LL << 60;
shortest_path<long long, INF> graph(N);
while (M--) {
int a, b, c;
cin >> a >> b >> c;
graph.add_edge(a, b, c);
}
graph.solve(s, t);
cout << graph.dist[t] << '\n';
問題例
Required by
Verified with
Code
Back to top page