考察
ある辺を消して最短距離が変わるのは、元の最短路がすべてその辺を通るときである。まず「少なくとも一つの最短路で使える辺」だけを残し、その中で「すべての最短路が避けられない辺」を探そう。今回は、後者を無向グラフの橋として一括で求められる。その理由は、正の重みによって最短路が始点からの距離を増やす向きにしか進まないことにある。
各辺を一つずつ削除して最短距離を計算し直すと、ダイクストラ法を 回行うことになり、最大 本の辺には間に合わない。一方、最短路が一つでも残れば答えは No なので、元の最短路に使われない辺は最初から調べる必要がない。
頂点 から各頂点 への最短距離を 、頂点 からの最短距離を 、元の の最短距離を とする。無向辺 の重みを とすると、少なくとも一つの最短路に含まれる条件は
である。左から順に「辺まで行く・辺を渡る・終点まで行く」距離を足している。二回のダイクストラ法で距離を求め、この等式を満たす辺だけを残した無向グラフを とする。
抽出辺を最短路で使う向きに見ると、 となる。重みは正なので距離は厳密に増え、その向きを付けた は DAG(有向閉路を持たないグラフ)になる。ただし、実際の橋判定では向きを付けずに扱う。距離順の性質は、その判定が正しいことを示すために使う。
注意したいのは、無向の迂回路があっても、その道をそのまま代替最短路にはできないことである。独自の小例として、すべて重み の二経路 、 に、辺 を加える。始点からの距離は が 、 が 、 が で、全辺が最短路上にある。それでも の無向迂回路 は最初に距離を減らし、長さも元の辺の に対して になる。この辺を避ける最短路は存在するが、それは迂回路の単純な差替えからは示せない。
そこで最短路を距離順に眺める。最短路上の頂点を始点から近い順に並べ、 と の間で切ると、最短路はその切れ目を一度だけ跨ぐ。切れ目を跨ぐ抽出辺が二本あれば、それぞれを使う最短路があり、一方を使う経路は他方を避ける。従って、全最短路で必須の辺には、それだけが跨ぐ切れ目が存在し、無向の橋になる。逆に抽出辺が橋なら、削除によって始点と終点が分かれ、最短路は残らない。双方向の論証は正当性で確認する。
実際の手順は次のとおりである。
- 全辺の重みを使い、 と を始点とするダイクストラ法で を求める。
- 各辺について両向きの距離等式を確認し、一方が成り立てば、元の辺 ID を保って の隣接リストへ無向辺として加える。
- に lowlink を適用し、橋の辺 ID を記録する。橋の列挙手順はlowlinkの単元を使う。
- 元の入力順に、 の橋なら Yes、それ以外なら No を出力する。
典型の発動条件
最短路部分グラフ
どれかの最短路に辺が含まれるかを調べるときは、始点・終点の両方から距離を求め、「その辺を通った長さが最短距離と一致するか」を確認する。始点からの距離を保つ辺だけを集めても、終点へ最短で続くとは限らない。両端距離の等式で、目的の二点間の最短路に載る辺へ絞る。
橋と必須経路
無向グラフで辺の削除による分断を一括で調べるときは、lowlinkによる橋の列挙が使える。特定の二点間で必須となるのは、その二点を分ける橋である。本問では、抽出辺のすべてが 最短路に載ることと、正重みによる距離順の性質を証明してから、橋と最短路の必須辺を対応させる。
問題固有の要素
本問の核心は、「距離等式で抽出した全辺がいずれかの 最短路に載る」と「最短路は距離順の切れ目を一度だけ跨ぐ」を組み合わせることである。別の抽出辺が同じ切れ目を跨げば、その辺を通る最短路が、調べている辺を避ける証拠になる。
単に DAG であることだけでは足りない。例えば に という行き止まりを付けた DAG では、無向にしたとき は橋でも、 の必須辺ではない。最短路の抽出では、このような終点へ続かない辺を除いている。
正当性
まず、辺 の重みを とする。最短路がこの辺を の向きに通るなら、その前後も最短なので が成り立つ。逆にこの等式が成り立つなら、最短の 、辺 、最短の を連結すると長さ の歩道を得る。頂点の重複があれば正の長さの閉路を除いて より短くできてしまうため、重複はなく、これは最短路である。逆向きも同様で、抽出条件は必要十分である。
抽出辺を通る最短路の接頭部分に注目すると、その向きでは である。このように距離の差と重みが等しい辺を tight な辺という。したがって抽出辺は距離が小さい側から大きい側へ一意に向き、有向閉路を持たない。さらに、これらの向きに沿った の経路は辺重みの和が距離差の和となり、途中の項が打ち消し合って になる。よって、この有向グラフの 経路と元の最短路は一致する。
ここから、抽出辺 を の向きに取り、無向の で橋であることと、全最短路で必須であることの同値性を示す。
橋なら全最短路で必須。 抽出条件により、 を通る最短路が一つ存在する。その経路から を除いた前半は と を、後半は と をそれぞれ結ぶ。 が橋なら削除後の は異なる連結成分にあるため、 も分かれる。すべての最短路は の辺だけを使うので、 を避ける最短路はない。
全最短路で必須なら橋。 最短路上にある頂点、すなわち を満たす頂点を の昇順に並べる。同距離の頂点の順は任意でよい。抽出辺は距離を厳密に増やすので、各最短路はこの並びの順に頂点を訪れる。先頭は 、末尾は である。
この並びを の直後で切り、前半の頂点集合を 、残りを とする。、 である。どの最短路も から へちょうど一度だけ移り、 へは戻らない。
もし とは別の抽出辺 もこの切れ目を跨ぐなら、抽出条件により を通る最短路が存在する。その最短路は で一度だけ切れ目を跨ぐため、同じ切れ目を跨ぐ を通れない。これは が全最短路で必須であることに矛盾する。従って を結ぶ抽出辺は 一本だけであり、 を除くと が分断される。すなわち は無向の橋である。
以上より、抽出辺以外と の橋でない辺には元の長さの最短路が残り、答えは No。 の橋にはそのような最短路が残らず、距離が増えるか到達不能になるため、答えは Yes となる。
実装上の注意
- 距離等式は無向辺の両向きについて調べる。未到達の距離を無限大として持つときは、その値を加算せず、必要な距離が有限の場合だけ比較する。元のグラフ全体が連結とは限らない。
- 距離は64 bit整数で持つ。単純路の長さは最大 になり、32 bit整数では足りない。
- の隣接辺には元の辺 ID を付け、DFSで親辺を除外するときもその ID を使う。抽出されなかった辺は常に No とする。
- 一本鎖ではすべての辺が橋となる。等長の二経路が分岐して再合流する部分では、その各辺は橋ではない。最短路上にない枝は、元のグラフで橋であっても No である。
- DFSの深さは最大 になる。再帰の上限が小さい実行環境では、帰りがけの lowlink 更新も保持する明示スタックで実装する。
復習の核
- 「どれかの最短路に使える」は両端距離の等式で、「すべての最短路で必須」は抽出後の構造で判定する。
- 無向の迂回路を、そのまま代替最短路と呼ばない。正重み・tight な辺・全抽出辺が終点までの最短路に載ることを確認する。
- 単調に進む経路では、順序の切れ目を何回跨ぐかに注目する。本問では「一度だけ」が別の辺を使う最短路の存在を保証する。
計算量と制約
時間
二回のダイクストラ法に 、抽出に 、lowlinkによる橋の列挙に 、出力に 。全体で 時間となる。距離順の並べ替えは証明で使うだけで、実装では不要である。
空間
元のグラフと の隣接リスト、距離配列、lowlinkの探索情報、橋の判定結果を合わせて 。ダイクストラ法の優先度付きキューも含む。
制約との対応
自己辺・多重辺のない無向グラフで、制限時間は3秒、メモリ制限は1024 MiBである。、 なので、辺ごとの最短路再計算を避け、二回の最短路計算と一回の橋列挙にまとめる。重みは の正整数であり、ダイクストラ法と、抽出辺に沿って距離が厳密に増える証明の両方に使う。重み を許す場合へ、同じ距離順の証明をそのまま適用しない。元の は到達可能なので は有限であり、削除後に到達不能となる場合も Yes に含める。
出典