ひとりで勝手にはじめた蟻本読書会 グラフ理論 最小全域木問題 クラスカル法 蟻本読書会の続きです。
ベルマンフォード法とは？
ベルマンフォード法は、重み付き有向グラフにおける単一始点の最短経路問題を解くアルゴリズムのひとつです。ダイクストラ法とちがって各辺の重みは負数でも使えます。辺の重みが非負数ならば優先度付きキューを併用したダイクストラ法の方が速いので、ベルマンフォード法は辺の重みに負数が存在するケースで主に使われます。名称は開発者であるリチャード・E・ベルマンと Lester Ford, Jr. にちなむ。
そのアルゴリズムは以下のとおりです。
初期状態で始点以外の頂点の始点からの距離は無限大にしておきます。各頂点の始点からの距離を最短距離と思われる距離に置き換えていきます。これを全辺を「緩める」とか「緩和」と表現します。これを繰り返すことで特殊な場合を除いて最短距離が正確にグラフ全体に伝播するため、最短経路を得ることができるのです。
では最短経路を得ることができない特殊な場合とはどのような場合なのでしょうか？
グラフに負閉路が含まれるとき
辺の重みの総和が負になるような閉路が存在するときは、その閉路を回り続けることでいくらでもコストを小さくすることができます。この場合、最短経路は存在しません。ベルマンフォード法は存在しない最短経路を求めることはできないのですが、負閉路を検出することはできます。
負閉路がなければ全辺を緩める処理を（頂点数 – 1）回繰り返せば、それ以上最短距離と思われる距離を更新することはできないはずです。そこでそれ以上処理を繰り返しても更新ができてしまう場合は負閉路が存在するということになります。
ベルマンフォード法の計算量は、頂点数と辺数をそれぞれ|V|と|E|とすると O(|V|・|E|) です。
基本問題
1,…,N の番号のついた N 個の頂点とそれらをつなぐ枝からなる有向グラフを考えます。ただし、自己ループと多重辺は考えません。枝 i は、頂点 a_i から頂点 b_i に向かう枝で、その重み（距離）は c_i です(1 ≦ i ≦ M)。
M 本の重み付き有向枝と頂点番号 s が与えられます。頂点 s からほかのすべての頂点へ向かう経路の最短距離を出力してください。頂点 s からの枝の移動では到達不可能な場合は inf と出力してください。
入力されるデータ
N M s
a_1 b_1 c_1
…
a_M b_M c_M2 ≦ N ≦ 100
1 ≦ M ≦ N × (N-1)
1 ≦ s ≦ N
1 ≦ a_i, b_i ≦ N
1 ≦ c_i ≦ 10
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, M, s; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; s = vs[2] - 1; } List<int>[] list = new List<int>[N]; List<int>[] wiights = new List<int>[N]; for (int i = 0; i < N; i++) { list[i] = new List<int>(); wiights[i] = new List<int>(); } for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int c = vs[2]; list[a].Add(b); wiights[a].Add(c); } long[] costs = new long[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; costs[s] = 0; // ループは N - 1 回回せばよいが負閉路を検出するため1回余分に回す bool updated = false; for (int i = 0; i < N; i++) { updated = false; for (int k = 0; k < N; k++) { for (int m = 0; m < list[k].Count; m++) { int v = list[k][m]; int w = wiights[k][m]; if (costs[k] == long.MaxValue) continue; if (costs[v] > costs[k] + w) { costs[v] = costs[k] + w; updated = true; } } } if (!updated) // これ以上更新されることはない（やるだけ無駄） break; } // N回 ループを回しても updated == true になるということは永久に更新される // つまり負閉路が存在する if (updated) { Console.WriteLine("負閉路が存在する"); return; } for (int i = 0; i < N; i++) { if(costs[i] < long.MaxValue) Console.WriteLine(costs[i]); else Console.WriteLine("inf"); } } } |
応用問題
N 頂点 M 辺の重み付き有向グラフがあります。
i(1 ≦ i ≦ M) 番目の辺は 頂点 a_i から 頂点 b_i を重み c_i で結びます。このグラフと駒を利用して、次の1人ゲームを行います。
駒を頂点 1 に置いて、プレイヤーのスコアを 0 とする。
プレイヤーは、頂点 a_i に駒があるとき、i 番目の辺を利用して頂点 b_i に移動する。移動後にプレイヤーのスコアが c_i 加算される。
頂点 N に駒があるときのみ、ゲームを終了できる。なお、与えられる有向グラフの上で頂点 1 から頂点 N に移動できることは保証されています。
プレイヤーがゲーム終了時のスコアを出来るだけ大きくするような行動を取ったとき、ゲーム終了時のスコアはいくつになるでしょうか？ ゲーム終了時のスコアをいくらでも大きくできる場合は inf と出力してください。
N M
a_1 b_1 c_1
a_2 b_2 c_2
…
a_M b_M c_M（ただし、2 ≦ N ≦ 1000
1 ≦ M ≦ min(N * (N – 1), 2000)
1 ≦ a_i, b_i ≦ N, -10^9 ≦ c_i ≦10^9 ）
ベルマンフォード法は最短経路だけではなく最長経路を求めることにも使えます。辺の重みの符号を反転させてコストが最小になるようにします。最後にコストの符号を反転させます。この場合は負閉路ではなく正の値の閉路を検出することができますが、注意する点があります。
ハマりどころ
頂点 1 から到達できない負閉路がある場合、これは存在しないものとして扱わなければなりません。そしてベルマンフォード法の中でもこのような負閉路は検出されません。
問題は次のケースです。頂点 1 から到達できる負閉路は存在するが、その負閉路からは頂点 N へとたどり着くことができない場合です。これも存在しないものとして扱わなければなりません。ところが普通にベルマンフォード法で処理をするとこの負閉路は検出されてしまいます。
そこで負閉路が検出された場合、inf と出力するべきか、その存在は無視するかを判断しなければなりません。負閉路が検出されなかった場合はそのまま得られた値（costs[N – 1]の符号を反転させたもの）を出力します。
負閉路が検出された場合、どこかで最短距離の更新がおこなわれますが、それが頂点 1 から頂点 N へ移動する場所とは無関係なところで起きるのであれば無視します。そこでさらに更新処理を N 回おこないます。そのさいに negative という配列を定義し、値の更新がおこなわれたらその頂点の negative を true に変更します。また negative が true である頂点から次の頂点にこれを伝搬させていきます。
無視してはならない負閉路の場合、この処理を N 回やれば negative は確実に頂点 N まで伝搬します。negative[N – 1] == false であれば costs[N – 1] の符号を反転させたものを結果として出力します。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, M; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; M = vs[1]; } List<int>[] list = new List<int>[N]; List<int>[] wiights = new List<int>[N]; for (int i = 0; i < N; i++) { list[i] = new List<int>(); wiights[i] = new List<int>(); } for (int i = 0; i < M; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int c = vs[2]; list[a].Add(b); wiights[a].Add(-c); } long[] costs = new long[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; costs[0] = 0; bool updated = false; for (int i = 0; i < N - 1; i++) { updated = false; for (int k = 0; k < N; k++) { for (int m = 0; m < list[k].Count; m++) { int v = list[k][m]; int w = wiights[k][m]; if (costs[k] == long.MaxValue) continue; if (costs[v] > costs[k] + w) { costs[v] = costs[k] + w; updated = true; } } } if (!updated) // これ以上更新されることはない（やるだけ無駄） break; } bool[] negative = new bool[N]; long ans = -costs[N - 1]; // 負閉路が検出された。ただし早合点してはならない。 if (updated) { for (int i = 0; i < N; i++) { for (int k = 0; k < N; k++) { for (int m = 0; m < list[k].Count; m++) { int v = list[k][m]; int w = wiights[k][m]; if (costs[k] == long.MaxValue) continue; // 負閉路があるがために更新が停止しない場所にnegativeフラグを設定 if (costs[v] > costs[k] + w) { costs[v] = costs[k] + w; updated = true; negative[v] = true; } // negativeフラグを伝搬させる if(negative[k]) negative[v] = true; } } } } // negativeフラグが 頂点 N まで伝搬しなかった場合は得られた値をそのまま出力する if(!negative[N - 1]) Console.WriteLine(ans); else Console.WriteLine("inf"); } } |
いわゆる牛ゲー
牛ゲーは蟻本に収録されている以下の問題のことです。牛ゲーと呼ばれているのは問題文に牛が登場することと、理解するのがちょっと難しいからです。
牛も列に並ぶとき、友達の近くに立つことを好みます。 1..N の番号が付けられた N (2 ≦ N ≦ 1,000) 頭の牛が直線に沿って立っており、餌を待っています。牛はつけられた番号と同じ順序で立っており、牛はかなり強引な場合があるため、2 頭以上の牛がまったく同じ場所に並ぶ可能性があります。
牛の中には、お互いが好きで互いに一定の距離内に並んでいたいと思う牛もいます。またお互いが本当に嫌いで、少なくとも一定の距離を置いて離れたいと思う牛もいます。 ML (1 ≦ ML ≦ 10,000) 制約のリストには、どの牛がお互いを好むかと許容する最大距離が記述されています。後続の MD 制約のリスト (1 ≦ MD ≦ 10,000) は、どの牛がお互いを嫌うかと許容する最小距離が記述されています。
あなたの仕事は、可能であれば、距離制約を満たす牛 1 と牛 N の間の可能な最大距離を計算することです。
サンプル入力
4 2 1
1 3 10
2 4 20
2 3 3最初の1行 の 3 つの整数: N、ML、MD
2行目からML+1行目までの各行には、スペースで区切られた 3 つの正の整数 A、B、D が含まれます。ただし、1 ≦ A ＜ B ≦ N です。牛 A と B は最大でも D (1 ≦ D ≦ 1,000,000) でなければなりません。ML+1行目から最後の行までの各行には、スペースで区切られた 3 つの正の整数 A、B、D が含まれます。ただし、1 ≦ A ＜ B ≦ N です。牛 A と B は少なくとも D ( 1 ≦ D ≦ 1,000,000) 離れています。
条件をみたす方法で牛を並べることができない場合は-1を出力します。 牛 1 と牛 N を任意に遠くに配置できる場合は -2 を出力します。それ以外の場合は、牛 1 と牛 N の間の可能な最大距離を出力します。
サンプル出力
27
始点 s からの各頂点の最短距離を d(x)、頂点 a から 頂点 b への辺の重みを w(a, b) とすると、任意の2点 i，j で i → j への(有向) 辺がある時、d(j) ≦ d(i) + w(i, j) が成り立ちます。これらの制約をすべて満たす d(i) の最大値が s と頂点 i の最短距離です。
問題文より d(i) ≦ d(i + 1) です。これは d(i) ≦ d(i + 1) + 0 と変形できるので、i + 1 → i への重み 0 の有向辺があると考えられます。頂点 a と b の距離を c 以下にするのであれば d(b) ≦ d(a) + c であり、これは a → b への重み c の有向辺があると考えられます。逆に頂点 a と b を c 以上離さなければならないのであれば d(a) + c ≦ d(b) であり、c を移項して d(a) ≦ d(b) – c と変形できます。これは b → a への重み c の有向辺があると考えられます。
ここから負の重みをもつ枝があるグラフの最短経路問題とみなすことができます。
少なくとも一定の距離を置いて離れたいと思う牛ばかりだと、牛 1 と牛 N の間の可能な最大距離はいくらでも長くすることができます。この場合はこのグラフには先頭から最後尾までたどり着く方法がありません。またグラフに負閉路が存在する場合は与えられた条件で牛を配置することはできないことを意味しています。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main() { int N, ML, MD; { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); N = vs[0]; ML = vs[1]; MD = vs[2]; } List<int>[] list = new List<int>[N]; List<int>[] wiights = new List<int>[N]; for (int i = 0; i < N; i++) { list[i] = new List<int>(); wiights[i] = new List<int>(); } for (int i = 0; i < N - 1; i++) { int a = i + 1; int b = i; list[a].Add(b); wiights[a].Add(0); } for (int i = 0; i < ML; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int c = vs[2]; list[a].Add(b); wiights[a].Add(c); } for (int i = 0; i < MD; i++) { int[] vs = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); int a = vs[0] - 1; int b = vs[1] - 1; int c = vs[2]; list[b].Add(a); wiights[b].Add(-c); } long[] costs = new long[N]; for (int i = 0; i < N; i++) costs[i] = long.MaxValue; costs[0] = 0; // ループは N - 1 回回せばよいが負閉路を検出するため1回余分に回す bool updated = false; for (int i = 0; i < N; i++) { updated = false; for (int k = 0; k < N; k++) { for (int m = 0; m < list[k].Count; m++) { int v = list[k][m]; int w = wiights[k][m]; if (costs[k] == long.MaxValue) continue; if (costs[v] > costs[k] + w) { costs[v] = costs[k] + w; updated = true; } } } if (!updated) break; } // 負閉路が存在する（配置不能） if (updated) Console.WriteLine(-1); else { if (costs[N - 1] < long.MaxValue) Console.WriteLine(costs[N - 1]); else Console.WriteLine(-2); // 任意に遠くに配置できる } } } |
