競プロ備忘録

アルゴリズムの実装を秒で思い出したい

端的にアイデアを載せて思い出します。

グラフ

 最短経路

  オーダー イデア
単一始点最短路 (Bellman–Ford法) O(VE) 更新出来なくなるまで全ての点を更新
V回目に更新した⇒負閉路が存在
単一始点最短路 (Dijkstra法) O(ElogV) 負辺なしのとき
始点からの距離最小の点⇒最短経路
k-最短路    
全点対間最短路 (Warshall–Floyd法) O(V3) dij=min(dij,dik+dkj)
全点対間最短路 (Johnson)    
経路復元 O(E) ゴールから近傍の点の始点からの最短距離とコストでルート判別
経路復元 O(V) 更新時、ひとつ前の頂点を記録

 全域木

  オーダー イデア
最小全域木 (Prim法) O(ElogV) 領域から最短の点
最小全域森 (Kruskal法) O(ElogV) 最短順に辺を追加、閉路を作らないように注意
最小直径全域木 (Cuninghame-Green)    
最小全域有向木 (Chu-Liu/Edmonds)    
最小シュタイナー木 (Dreyfus-Wagner)    

 フロー・カット

  オーダー イデア
最大流 (Ford-Fulkerson) O(FE) 最大流-最小カット定理
最大流 (Edmonds-Karp)    
最大流 (Dinic)    
最大流 (Goldberg-Tarjan)    
無向グラフの全域最小カット (Nagamochi-Ibaraki/Stoer-Wagner)    
Gomory-Hu 木    
最小費用流 (Primal Dual)