1 辺を除いたときの最短路長

問題設定

無向グラフ , 非負の辺重み , 始点 , 終点 が与えられる。 各 について、 上での 最短路長を求めよ。

この問題を の時間計算量で解くアルゴリズムを説明する。

本質的に同じ問題が https://codeforces.com/contest/1163/problem/F で出題されており、解説するアルゴリズムは tutorial にあるものと同じである。 ただしこの tutorial には証明がないため注意。

アルゴリズム

議論を簡易にするため、まず辺重みは を含まないものとする。 このとき、以下のアルゴリズムが正しく答えを計算する。

まず、 を始点とする最短路木 と を始点とする最短路木 をとる。 ただし、両者で パス部分が一致するようにし、それを とおく。 を取り除いたときの最短路長は明らかに である。

各辺 に対し以下の処理を行う。

• における と の LCA、すなわち における パスが と分岐する頂点を とする。
• 同様に、 における と の LCA を とする。
• 上で ならば、 に沿って と移動し、 を通り、 に沿って に至るパスは と の間にある各辺 を通らない。よってそれらの辺に対し、 を取り除いた際の最短路長の候補に を追加する。

ただし、 は順序対として扱う、すなわち にも上記の処理を行うものとする。 処理が全て終わったとき、候補の中で最短のものが求める答えである。 候補の中での最短の計算は、双対セグメント木を使ったり、std::set などのデータ構造を使って imos 法のような処理を行えばよい。

証明

辺 を固定し、 に関する答えが正しく計算されることを示す。

補題

任意の頂点 に対し、以下の両方が成り立つことはない。

• における パスが を含む
• における パスが を含む

証明(補題)

同時に成り立つ が存在すると仮定する。 パスと パスが で交差しているが、 の前後でパスを組み替えると、合計長が真に短いパスの組が得られるため、それぞれが最短路だったことと矛盾する。 を使用したことに注意せよ。

における パスが を 含まない ような を 、 における パスが を 含まない ようなものを と呼ぶことにする。 補題より、全ての頂点は であるか である。 両方に該当する頂点は好きな方に割り当てておく。

における 最短路を つとり とする。 は であり は であることから、 上の辺 であって が , が であるものが存在する。 また、 の関係から である。 するとアルゴリズム中でこの に対して構成されるパスは を通らず、かつ と同じ長さであるため、 に対する答えが正しく計算される。

辺の長さが を含む場合

この場合、 と の取り方によってはアルゴリズムが誤った答えを返すことがある。 補題が成り立つように適切に取ればよいが、最も証明が明らかな方法は重み の辺を重み にすることである。

注意

有向グラフに対してはこのアルゴリズムは正しく動作しない。 証明において破綻するのは、補題で パスと パスの組み換えを行った部分である。