ダイクストラ法とその制約
ダイクストラ法はグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムです。1959年エドガー・ダイクストラによって考案されたアルゴリズムでOSPFなどのインターネットルーティングプロトコルや、カーナビの経路探索や鉄道の経路案内においても利用されています。
時間計算量は頂点数を V、辺の数を E としたとき、O((V + E) × log(V)) です。log(V)がつくのは実装に優先度つきキューを用いるからです。
注意しなければならないのは、負の重みをもつ辺があるグラフでは使えないという制約があることです。では負の重みをもつ辺があるグラフで最短経路問題を解くときはどうすればよいのでしょうか？
ベルマンフォード法はひとつの選択です。ベルマンフォード法の時間計算量は O(V × E) です。ダイクストラ法と比べると計算量が増えてしまいますが、こちらは負の重みをもつ辺があっても使えます。
とはいえ、同じグラフで何度も最短経路問題を解かなければならない場合は計算量が少ないダイクストラ法を使いたいものです。うまくグラフを負辺を持たないグラフに変換する方法はないものでしょうか？
これに回答を与えるのがポテンシャルです。
ポテンシャルとは？
頂点 u から頂点 v への有向辺が張られていてその重みを w(u, v) で表すことにします。このとき、頂点 i に重み p(i) をもたせることで w(u, v) ≧ p(v) – p(u) が常に成立する場合、実行可能ポテンシャルが存在すると定義します。
w(u, v) + p(u) – p(v) を被約コスト c(u, v) と定義します。また被約コストによって重み付けられたグラフを被約グラフと呼ぶことにします。
パス上の辺の重みの総和と被約コストの総和の差は端点のみに依存します。頂点 v1, v2, …, vk を通るパスの辺の被約コストの総和を計算してみると
c(v1, v2) + c(v2, v3) + … + c(v{k- 1}, vk)
= {w(v1, v2) + p(v1) – p(v2)} + {w(v2, v3) + p(v2) – p(v3)} + … + {w(v{k – 1}, vk) + p(v{k – 1}) – p(vk)}
= w(v1, v2) + w(v2, v3) + … + w(v{k – 1}, vk) + p(v1) – p(vk)
となり、移項すると
(v1, v2) + w(v2, v3) + … + w(v{k – 1}, vk) = c(v1, v2) + c(v2, v3) + … + c(v{k- 1}, vk) + p(vk) – p(v1)
となります。この式が意味するものは s から t までの最短経路長は 被約グラフの s から t までの最短経路長に t のポテンシャルを加え s のポテンシャルを引いたものであるということです。
また負閉路を持たないことと、実行可能ポテンシャルが存在することは同値です。
E – Skiing
問題の概要
スキー場には N 個の広場があり、広場 i の標高は H[i] である。
2 つの広場を双方向に結ぶ M 本の坂があり、i 本目の坂は広場 U[i] と広場 V[i] を双方向に結んでいる。「楽しさ」を以下のように定義する。
広場 X が広場 Y より標高が真に高い場合、その標高差、すなわち H[X] – H[Y] だけ楽しさが増加する。
広場 X が広場 Y より標高が真に低い場合、その標高差の 2 倍、すなわち 2(H[Y] – H[X]) だけ楽しさが減少する。
広場 X と広場 Y の標高が等しい場合、楽しさは変化しない。
楽しさは負の値になることもある。最初、広場 1 におり、楽しさは 0 である。0 本以上のいくつかの坂を移動した後に好きな広場で行動を終えることができるとしたとき、楽しさとしてありうる最大の値を求めよ。
楽しさの -1 倍をコストとみなすことで、問題文は「頂点 1 からの最小移動コストが最小となる頂点の移動コストを求めよ」という最短経路の問題に言い換えることができます。
この問題を直接ダイクストラ法で解くことはできません。このグラフには負のコストをもつ辺が含まれているからです。一方で、ベルマンフォード法では計算量が O(NM) となるので間に合いません。そこで、ポテンシャルを用いてこの問題をダイクストラ法が適用できる形にすることを考えます。
実は標高がポテンシャルとして使えます。
頂点 v1, v2 の標高を h1, h2 としたとき、h1 ≧ h2 なら以下のように辺が張られます。
頂点 v1 から 頂点 v2 へ 重み h2 – h1 の辺
頂点 v2 から 頂点 v1 へ 重み (h1 – h2) × 2 の辺
ポテンシャルの定義と比較してみると以下の不等式が成立しています。
頂点 v1 から 頂点 v2： h2 – h1 ≧ h2 – h1
頂点 v2 から 頂点 v1： (h1 – h2) × 2 ≧ h1 – h2
被約コストは以下のようになります。
頂点 v1 から 頂点 v2： h2 – h1 – (h2 – h1) = 0
頂点 v2 から 頂点 v1： (h1 – h2) * 2 – (h1 – h2) = h1 – h2
なので以下のような被約グラフを構築します。
頂点 v1 から 頂点 v2： 重み 0 の辺を張る
頂点 v2 から 頂点 v1： 重み h1 – h2 の辺を張る
被約グラフにおいてダイクストラ法で頂点 0 から各頂点への最短経路長を調べます。各頂点への最短経路長が求まったらそれらに各頂点の標高を加えて頂点 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 |
class Program { static void Main() { int[] nm = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int N, int M) = (nm[0], nm[1]); int[] H = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); // 被約グラフを構築する List<(int, long)>[] G = new List<(int, long)>[N]; for (int i = 0; i < N; i++) G[i] = new List<(int, long)>(); for (int i = 0; i < M; i++) { int[] uv = Console.ReadLine().Split().Select(_ => int.Parse(_)).ToArray(); (int high_idx, int low_idx) = (uv[0] - 1, uv[1] - 1); if (H[high_idx] < H[low_idx]) (high_idx, low_idx) = (low_idx, high_idx); G[high_idx].Add((low_idx, 0)); G[low_idx].Add((high_idx, H[high_idx] - H[low_idx])); } // 被約グラフにおける各頂点への最短経路長を求める PriorityQueue<(int, long), long> pq = new PriorityQueue<(int, long), long>(); pq.Enqueue((0, 0), 0); long[] costs = new long[N]; Array.Fill(costs, long.MaxValue); while (pq.Count > 0) { var pair = pq.Dequeue(); int cur_idx = pair.Item1; long cur_cost = pair.Item2; if (costs[cur_idx] <= cur_cost) continue; costs[cur_idx] = cur_cost; foreach (var edge in G[cur_idx]) { int next_idx = edge.Item1; long next_cost = cur_cost + edge.Item2; pq.Enqueue((next_idx, next_cost), next_cost); } } // 被約グラフにおける各頂点への最短経路長から元のグラフの最短コストを求める for (int i = 0; i < N; i++) costs[i] += H[i] - H[0]; // 最小値の符号を反転させたものが解 Console.WriteLine(-costs.Min()); } } |
ポテンシャルを求めて被約グラフを構築するには？
負の重みをもつ辺があるグラフからポテンシャルを求め、被約グラフを構築するにはどうすればよいでしょうか？
ポテンシャルを求めるにはベルマンフォード法をつかいます。
まず超頂点 S を追加し、そこから各頂点へ重み 0 の有向辺を張り、S から各頂点への最短距離を求めます。この最短距離がポテンシャルとなります。なので負の重みをもつ辺が存在しない場合、ポテンシャルは 0 です。
なぜこの方法でポテンシャルを求めることができるのでしょうか？
h は 超頂点 S からの最短距離、w(u, v) は u から v までの距離なので、任意の辺 u → v について h[v] ≦ h[u] + w(u, v) が成立します。これを変形すると、w(u, v) ≧ h[v] – h[u] となります。これはポテンシャルの定義と一致します。
ポテンシャルを求めることができたら被約グラフを構築して最短経路長を求めます。
|
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 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 |
class Program { /// <summary> /// ポテンシャルを求める /// </summary> /// <param name="G"></param> /// <returns>負閉路ありのときは空の配列を返す</returns> static long[] TryGetPotential(List<(int, long)>[] G) { int v_cnt = G.Length; long[] P = new long[v_cnt]; // 仮想始点 s から全頂点へ 0 コストの辺を張る // これは全頂点の初期距離を 0 にして、Bellman-Ford を開始するのと同じ for (int i = 0; i < v_cnt; i++) P[i] = 0; // 辺を緩和する。どこも更新されなくなったら終了 // (頂点の個数)回よりも多く繰り返しても更新されつづけるのであれば負閉路が存在する // 負閉路が存在する ⇔ 実行可能ポテンシャルが存在しない bool updated = false; for (int i = 0; i < v_cnt + 1; i++) { updated = false; for (int cur_idx = 0; cur_idx < v_cnt; cur_idx++) { long cur_dist = P[cur_idx]; foreach (var edge in G[cur_idx]) { int next_idx = edge.Item1; long next_dist = cur_dist + edge.Item2; if (P[next_idx] > next_dist) { P[next_idx] = next_dist; updated = true; } } } if (!updated) break; } if (updated) // 負閉路が存在する return new long[0]; else return P; } /// <summary> /// 負の辺があるかもしれないグラフからポテンシャルをもとめ、構築された被約グラフを返す /// </summary> /// <param name="G"></param> /// <returns>被約グラフとポテンシャルのタプル</returns> static (List<(int, long)>[] ReducedGraph, long[] Potential) BuildReducedGraph(List<(int, long)>[] G) { int v_cnt = G.Length; long[] P = TryGetPotential(G); if (P.Length == 0) return (new List<(int, long)>[0], new long[0]); List<(int, long)>[] reducedG = new List<(int, long)>[v_cnt]; for (int i = 0; i < v_cnt; i++) { reducedG[i] = new List<(int, long)>(); foreach (var edge in G[i]) { int next_idx = edge.Item1; long next_dist = edge.Item2 + P[i] - P[edge.Item1]; reducedG[i].Add((next_idx, next_dist)); } } return (reducedG, P); } /// <summary> /// 負の辺があるかもしれないグラフから被約グラフを構築してダイクストラ法で最短経路長を求める /// </summary> /// <param name="G"></param> /// <param name="start">始点</param> /// <returns>各頂点への最短経路長</returns> static long[] DijkstraNegative(List<(int, long)>[] G, int start) { int v_cnt = G.Length; var res = BuildReducedGraph(G); if(res.ReducedGraph.Length == 0) return new long[0]; List<(int, long)>[] reducedGraph = res.ReducedGraph; long[] potential = res.Potential; PriorityQueue<(int, long), long> pq = new PriorityQueue<(int, long), long>(); pq.Enqueue((start, 0), 0); long[] dists = new long[v_cnt]; Array.Fill(dists, long.MaxValue); while (pq.Count > 0) { var pair = pq.Dequeue(); int cur_idx = pair.Item1; long cur_cost = pair.Item2; if (dists[cur_idx] <= cur_cost) continue; dists[cur_idx] = cur_cost; foreach (var edge in reducedGraph[cur_idx]) { int next_idx = edge.Item1; long next_cost = cur_cost + edge.Item2; pq.Enqueue((next_idx, next_cost), next_cost); } } for (int i = 0; i < v_cnt; i++) dists[i] += potential[i] - potential[start]; return dists; } } |
