競プロでアルゴリズムを勉強したい

ワーシャルフロイド法とは 　グラフのすべての頂点の組 (u,v) に対して、u から v への最短距離を求めるアルゴリズム。 　辺のコストが負でもよい。 ワーシャルフロイド法のアルゴリズム 頂点 u から頂点 v への距離 d[u][v] を u から v への辺 (u,v) のコストで初期化、辺がなければ無限大としておく。また、頂点 u から頂点 u 自身への距離 d[u][u] は 0 としておく。 以下の操作を k=0, 1, …, n-1 (頂点数: n) の順に行う。 グラフのすべての頂点の組 (u,v) に対して、通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに限定したときの最短距離を求め、その距離が d[u][v] より小さければ d[u][v] をその距離で更新。 距離 d[u][u] < 0 となる頂点 u が存在すれば、負閉路が存在する、存在しなければ負閉路も存在しない。 説明 アルゴリズムの 2. の操作 (図) 　例えば、こんなグラフがあったとする。 　例えば、k=2, u=4, v=6 なら、以下の範囲で頂点 u から頂点 v への最短距離を調べる。(頂点集合 {0, 1, 2} ∨ {4, 6}) 　これを、(k, u, v)=(0, 0, 0), (0, 0, 1), …, (0, n-1, n-1), (1, 0, 0), …, (1, n-1, n-1), …, (n-1, 0, 0), …, (n-1, n-1, n-1) の順に調べていく。(一応、k が k=0, 1, …, n-1 の順なだけで (k, 0, 0), (k, 0, 1), …, (k, n-1, n-1) は順不同。) 通れる頂点を限定したときの最短距離ってどう求めるの？ 　[通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに限定したときの最短距離 (以下、d k [u][v])] は、すべての頂点の組 (u, v) で、[通れる頂点を頂点集合 {0, 1, …, k-1} ∨ {u, v} の頂点のみに限定したときの最短距離 (以下、d k-1 [u][v])] を求められていれば簡単に求められる。 　まず、[通れる頂点を頂点集合 {0, 1, …, k} ∨ {u, v} の頂点のみに...

ベルマンフォード法 ベルマンフォード法とは 　グラフのすべての頂点に対して、ある頂点からの最短距離を求めるアルゴリズム。 　 ダイクストラ法 と違い、辺のコストが負でもよい。 ベルマンフォード法のアルゴリズム スタート地点の頂点からその頂点自身への距離は 0 とし、それ以外の頂点の距離は無限大としておく。 以下の操作を n-1 回 (頂点数: n) 行う。最後に、以下の操作をもう 1 回行う。 すべての辺に対して、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。 最後の 1 回の操作で、[終点の距離] > [始点の距離+辺のコスト] である辺があった場合、与えられたグラフに負閉路が存在する、なかった場合、負閉路は存在しない。 例と説明 ベルマンフォード法の動き (GIF) 説明 　スタート地点を頂点 0 とする。 　スタート地点の距離は 0 で初期化する。 　この時点で、スタート地点から各頂点へ 0 ステップ (0 回の移動) で行ける経路のうち最短の距離が求められている。([0 ステップで行ける = 移動しないで行ける] なので、頂点 0 のみ行ける (距離は ０)。) 　(1回目) すべての辺に対して、それぞれ [終点の距離] > [始点の距離+辺のコスト] なら [終点の距離] を [始点の距離+辺のコスト] で更新する。(今回は、辺 (0,1), (0,2), (0,4), (2,1), …, (4,3) の順に更新しているが、順番は関係ない。) 　この時点で、スタート地点から各頂点へ 1 ステップ以下で行ける経路の最短の距離 以下の距離 に更新されている。(もともと各頂点で 0 ステップで行ける経路の最短距離が求められている。辺を走査すれば +1 ステップの距離がわかるため、各頂点への距離は、少なくとも 0 ステップ または 0+1 ステップで行ける経路のうち最短の距離 以下 には更新される。( 以下 としているのは、辺の走査順によっては、+2 ステップ以上調べられる場合があるからである。(例えば、辺 (0,4) のあとに辺 (4,3) を調べているため、頂点 3 は、この時点で、2 ス...