不等式と最短路の話

アルゴリズム
  • d[i] + e(i,j) >= d[j]

というような形の式が何個か制約として与えられたとき、d[s]=0としてd[k]の最大値を求めましょうという話

例

例1
  • d[0] + 5 >= d[1]
  • d[0] = 0

のとき、d[1]の最大値は5

例2
  • d[1] + 3 >= d[0]
  • d[0] = 0

のとき、d[1]の最大値はない（無限に大きい）

例3
  • d[0] + 4 >= d[1]
  • d[1] - 5 >= d[0]
  • d[0] = 0

のとき、d[1]の最大値はない（この制約を満たすようなd[1]はない）

2番目と3番目の例はどちらも最大値はないが、意味が違うことに注意

グラフの最短路について

  • d[i] = グラフGにおける、頂点sから頂点iまでの最短距離

とする。このとき

  • d[k] + e(k,i) >= d[i]　　　　・・・(1)

を満たす。ここでe(k,i)は頂点kから頂点iに伸びる辺の距離である（多重辺を認める場合場合はその中の最小）。

(1)の証明は、もし

  • d[k] + e(k,i) < d[i]

とすると、頂点kから頂点iに、e(k,i)を使って辿ることによって、頂点iへd[i]より小さな距離で辿れることになり、d[i]が最短距離であることに矛盾するから。

また、d[i]は(1)の制約を満たす中で最大値を取る。
なぜなら、(i!=sで)最短距離の定義より（W-Fを思い出すと）

  • d[i] = min(d[k] + e(k,i))

であり、d[i]が右辺より大きければ(1)を満たさなくなるから。

よってグラフの最短路を求めることは冒頭に上げた問題を解くことと等しいといえる。

実際

  • d[i] + e(i,j) >= d[j]

という制約が与えられたら（ちょっと違っても変形する）、頂点iから頂点jに辺をコストe(i,j)で張る。

s=0で考えるのならば、sからの単一始点最短路を求めればよい。

負辺があるのでベルマンフォードを使う。

いろいろ

基本的に

d[i] = INF　なら、iは無限に大きくすることが出来る

制約を満たせないかどうか

負閉路が存在したら、制約を満たすような解は無い

基準点がどこかわからない

頂点を１つ追加し、全ての頂点にコスト0の辺を張り、追加した頂点からの最短路を求める。

順番が一意に定まるかどうか

全点対間距離を求め、全てのi,j(i!=j)について、d(i,j)>=0かつd(j,i)>=0な組が無ければ一意に決まる。
(証明)
d[i],d[j]は

  • d[j]-d(i,j)<=d[i]<=d[j]+d(j,i)

を満たすように決めることが出来る。
もしd(i,j)>=0かつd(j,i)>=0ならば、d[i]>d[j]ともd[j]>d[i]とも決めることが出来るので一意に定まらない。
逆にd(i,j)<0ならば、必ずd[i]>d[j]となるし、
d(j,i)<0ならば、必ずd[i]0より必ずこの不等式を満たすようなd[i]があり、d(i,j)<0かつd(j,i)<0となるようなこともない。

練習問題

以下はe(i,j)が1か0なのでトポロジカルソートで出来る

まとめ

実感がわかなくてよく分からん。