最短経路問題

グラフ理論

最短経路問題（shortest path problem）とは、与えられた重み付きグラフに対し2頂点を結ぶ重み最小経路を求める問題である。これを最短経路と呼ぶ。 

en.wikipedia.org

〇本稿では、

・路の距離(distance)とは路に含まれる重み(length/weight)の総和のこととする。

・経路長とは路に含まれる辺の数とする。

・vがuからｎ手到達可能とは、経路長n以下のuからvへの路が存在することとする。

 ふつう、距離というと本稿での経路長を表すようなので混同に注意せよ。

 

〇最短経路問題に対応して、最長経路問題が考えられる。これは、辺の重みを-1倍することでお互いに変換することができる。

 

SSSPとその解法

 単一始点最短経路問題（single-source shortest path problem / 以下SSSP）とは、与えられた重み付きグラフの固定された頂点ｖに対し、ｖから他の全ての頂点への最短経路を探索する問題のことである。

簡単な考察により以下がわかる：

・双対的な問題として、単一終点最短経路問題を考えることができる。これは無向グラフにおいてはSSSPと同一である。（やさしい）有向グラフに対しても辺の向きを逆転させたグラフにおけるSSSPに帰着される。

・無向グラフにおけるSSSPは、その無向辺を2つの有向辺に置き換えることで、有向グラフにおけるSSSPに帰着される。

 

現在知られているSSSPを解くアルゴリズムとして、代表的に以下が挙げられる。

ダイクストラ法（Dijkstra's algorithm）

ダイクストラ法（Dijkstra's algorithm）は、辺の重みが非負実数値の有向グラフの場合に適用できるアルゴリズム。wikiからの疑似コードのコピペ：

グラフ  、スタートとなる頂点  、および  から  への辺の長さ  を入力として受け取る
// 初期化 
for (  )
     ならば  、それ以外は 
     「無し」
    

// 本計算
while (  が空集合ではない )
   から  が最小である頂点  を取り出す
   for each (  からの辺がある各  )
       
       if (  )

 

ただし、Ｑは優先度付きキューの構造を持つとする。*1

このキューの構築、変更、検索の時間計算量に依存してダイクストラ法の時間計算量は変化する。時間がかかる順に、

・素朴な配列であり、毎回最小頂点を探す場合、O(|V|^2)

・バイナリヒープである場合、O((|E|+|V|)log|V|)

・フィボナッチヒープである場合、O(|E|+|V|log|V|)

このことの証明にはヒープの構築・検索などの計算量を調べればよいが、それは読者の演習とする。  いつか他の記事でデータ構造を扱う。（きっと）

■ダイクストラ法により最短経路が求まることは次のように示される：

頂点vまでの最短距離をsh(v)とする。Ｑから頂点vが取り出された瞬間、sh(v)=d(v)であることをvの帰納法で示す。もしsh(v)<d(v)なら、真の最短経路s→u1→…→un=vが存在する。s,u1..uiはすでにＱから取り出された後、ui+1はまだＱから取り出されていないとすれば、sh(uj)=d(uj)　(1≦j≦i≦n)となっている。（このようなiは一意に定まる。i=nのときはui+1についての文は無視せよ。）vはQ(v)が最小なので、Q(v)≦Q(ui+1)。これと辺の重みの非負性よりui+1→…→un=vは重み０の道であるほかない。よって、sh(v)=sh(ui)+length(ui,ui+1)=d(ui)+length(ui,ui+1)。uiはQから取り出されているので、d(v)≦d(ui)+length(ui,ui+1)=sh(v)となり、矛盾する。

重みの非負性が失われるとダイクストラ法が機能しないことは以下の反例を考えればよい。

f:id:nessinverse:20190114021934p:plain

 

〇話題：A*探索アルゴリズム（A-star search algorithm）以下、A*とする。

地図があり、始点と終点が与えられたとする。最短経路は、始点と終点を結ぶ直線に近いだろう。このように付加的な情報があった場合、それを利用した方が高速にルートを探索可能である。ヒューリスティックスとは、高速に近似解を求めるアルゴリズムのことをいう。

A*は非負重み有向グラフのほかに、ヒューリスティック関数h:V→R≧0を入力として受け取る。ただし、hをヒントとしてA*は路の探索を行うが、h=0の場合はダイクストラ法そのものとなる。よって、A*はダイクストラ法の拡張である。また、A*はhがいかなる関数であったとしても、最後まで計算すれば最短経路を出力するアルゴリズムである。

 

要請：有向グラフは非負重み、かつ頂点nから終点までの最短距離をh*(n)としたとき0≦h(n)≦h*(n)（この性質を、ｈが許容的という）

//f(n):始点→頂点ｎ→終点といくときの最短距離の概算値
//h(n):ヒューリスティック関数、頂点ｎ→終点までの最短距離の推定値
//OPEN:作業中の頂点たち
//CLOSE:解決（仮）した頂点たち

OPENリスト、CLOSEリストを空にする
OPENリストに始点を追加、f(始点)=h(始点)
while(true)
    if (OPEN.isempty()) error "始点から終点への路は存在しない"
    OPENの中でf(n)が最小の頂点vを取り出す

    if(isgoal(v)) break
    else CLOSEリストにvを追加

    foreach w : vに隣接する頂点
        newf(w)=f(v)-h(v)+h(w)+length(v,w)
        if(w∈OPENでもw∈CLOSEでもない）
            f(w)=newf(w), OPENリストにwを追加、parent(w)=v
        elseif(w∈OPEN)
            f(w)=min(f(w),newf(w)),もしnewfのほうが小さかったならparent(w)=vと変更
        elseif(w∈CLOSE)
            if(f(w)>newf(w))
                f(w)=newf(w),CLOSEからOPENへwを移動,parent(w)=v

parentをたどって最短経路を出力

 

■証明：始点から到達可能ならOPENに一度は入る。無限ループにならないことは、f(w)として取り得る値の可能性が有限通りしかないことでわかる。

出力が最短であることのアイデア：終点がOPENに入る時、f(終点)の値は実在する路の距離となる。これが最短路でない場合、hが許容的なことにより、別の路の計算が優先される。これにより、終点が取り出される前にf(終点)は最短距離に更新されるから、示される。

・もし、アルゴリズムに時間制限があれば途中で計算を打ち切り、OPENに入っている”計算途中”のf(終点)とparentを見て近似解を得ることができる。hがh*に近いほど、効果的であると期待される。（常に、より効果的であることまでは保証されない）

・A*の計算量は、OPEN/CLOSEに使うデータ構造の時間計算量に強く依存する。詳しくは論文などを参照。

 

ベルマンフォード法（Bellman-Ford algorithm）

ベルマンフォード法（Bellman-Ford algorithm）は、辺の重みが任意である有向グラフに用いられるアルゴリズム。wikiから疑似コードのコピペ：

procedure BellmanFord(list vertices, list edges, vertex source)
   // この実装では、グラフを頂点のリストと辺のリストで表す。
   // そして、各頂点の distance と predecessor 属性が
   // 最短経路を格納するよう変更していく。

   // Step 1: グラフの初期化
   for each vertex v in vertices:
       if v is source then v.distance := 0
       else v.distance := infinity
       v.predecessor := null
   
   // Step 2: 辺の緩和を反復
   for i from 1 to size(vertices) - 1:       
       for each edge uv in edges: // uv は u から v に向かう辺
           u := uv.source
           v := uv.destination             
           if v.distance > u.distance + uv.weight://u.disがinfのときfalseと約束
               v.distance := u.distance + uv.weight
               v.predecessor := u

   // Step 3: 負の重みの閉路がないかチェック
   for each edge uv in edges:
       u := uv.source
       v := uv.destination
       if u.distance + uv.weight < v.distance:
           error "Graph contains a negative-weight cycle"

 

始点から到達可能な負閉路が存在すれば、最短経路は存在しない。（負閉路を回り続けることで、いくらでも距離を小さくできるため）実は、ベルマンフォード法は負閉路の検出にも用いることができる。

v.distance > u.distance + uv.weightのときに、v.distanceを上のように更新する作業を、辺uvの緩和(relaxation)という。このアルゴリズムは、（全辺の緩和）を頂点数-1回行うため、時間計算量は明らかにO(|V||E|)である。

■頂点vへの最短距離をv.distanceが与えることの証明：

forサイクルをi回繰り返した時にv.distanceは、vが始点からi手到達可能のとき、「始点からvまでの何らかの路の距離である、かつ、始点からvまでの高々i個長の路全体の中で最短のものの距離以下である」を示す。

iの帰納法を用いよう。始点からvへの高々i+1個長の路全体の中で最短のもののをs→…→u→vとする。この制限s→…→uは始点からuへの高々i個長の路全体の中で最短のものである。forループi+1回目の緩和によって、v.distanceは始点からvへの高々i+1個長の路全体の中で最短のものの距離以下であることがわかった。

これにより、負閉路がない場合について証明される。実際、任意の頂点vへの最短経路は、（重み０の閉路を取り除くことで）高々頂点数-1の長さしか持たないから、v.distanceは最短距離となる。

■負閉路がある場合はStep３で判定できることの証明：

緩和不能なら、任意の閉路v0→v1→…→vn→v0に対して、vi.distance <= vi-1.distance + vi-1vi.weight (i=0のとき、i-1=nと約束する)が成り立つ。両辺をi=0..nにわたって足すことで、0<=v0v1.weight+...+vnv0.weightが得られ、負閉路がないことが示された。

ベルマンフォード法は、ダイクストラ法よりも低速であるから、一般に重み負の辺をもつグラフにのみ用いた方がよい。

〇計算量半減改良

頂点をv1...vnとし、有向辺全体を、「vi→vj(i<j)全体」「vi→vj(i>j)全体」の2グループA,Bに分けよう。

・操作Ｘ：v1...vnの順に、これを始点とするAの辺をすべて緩和することを繰り返す。

・操作Ｙ：vn...v1の順に、これを始点とするBの辺をすべて緩和することを繰り返す。

Xからはじめて、X,Yを交互に計n-1回行えば、最短経路が求まる。このことは上と同様の議論でわかるので、読者の演習とする。

 

その他のアルゴリズム

・辺の重みがすべて等しい場合には、幅優先探索を用いることができる。（やさしい）時間計算量はO(|E|+|V|)。

 

・DAG（有向非巡回グラフ）に対しては、トポロジカルソートを用いて計算量を減らすことができる。時間計算量はO(|E|+|V|)。

vを始点とし、頂点集合はトポロジカル順序v1,v2,...vnとする。DAGなのでi<jに対しvj→viなる有向路はないことに注意すれば、vよりトポロジカル順序-小な辺への有向路は存在しない。よって、v1=vとして一般性を失わない。

v.distanceを、vにおいて0,それ以外において∞となるよう初期化する。

pをトポロジカル順に頂点集合を走る変数とせよ。各pに対し、「pから有向辺が出ているすべての頂点qに対し、辺pqを緩和する」forループを走らせる。これによりvからの最短長が求まることは、p=viとなっているときにすでにvi.distanceの値が最短経路であることをiの帰納法で示せばよい。（やさしい）

 

・正整数重み無向グラフに対し、Thorup's Linear Time Algorithmという線型時間計算量のアルゴリズムの存在が知られている。（しかし、実装が困難な上に普通のサイズのグラフではダイクストラ法のほうがまだ高速らしく、実用的でない模様。私は内容を追ったことはないですが、面白そうなので興味ある方はぜひ検索してみてください。）

Implementation of Thorup's Linear Time Algorithm for Undirected Singl…

 

APSPとその解法

全点対最短経路問題（all-pairs shortest path problem / 以下APSP）とは、与えられた重み付きグラフに対し、全ての頂点の組に対してその間の最短経路を探索する問題のことである。

・APSPが解ければ明らかにSSSPも解ける。（しかし、一般にSSSPを解くのにAPSPのアルゴリズムを使うのはオーバーキルすぎて時間・空間計算量がかさむ。）

・無向グラフにおけるAPSPは、SSSPと同様その無向辺を2つの有向辺に置き換えることで、有向グラフにおけるAPSPに帰着される。

 

現在知られているAPSPを解くアルゴリズムとして、代表的に以下が挙げられる。

 

ワーシャルフロイド法（Floyd-Warshall algorithm）

ワーシャルフロイド法（Floyd-Warshall algorithm）は、重みとして任意の実数値をとる有向グラフに用いられるアルゴリズム。

// グラフはV={1,...,n}のn頂点有向グラフとし、辺ijの重みをlength(i,j)とする。

// 初期化
for each i ∈ {1,...,n}
    for each j ∈ {1,...,n}
        di,j ← 辺ijが存在すればlength(i,j),i=jなら0,そうでなければinf

// 本計算
for each k ∈ {1,...,n}
    for each i ∈ {1,...,n}
        for each j ∈ {1,...,n}
            if (di,j > di,k + dk,j) // 右辺のいずれかがinfならfalseと約束する
                di,j ← di,k + dk,j

// 負閉路検出
for each i ∈ {1,...,n}
    if (di,i < 0)
        error "Negative cycle exists"

時間計算量は明らかにO(|V|^3)。これはベルマンフォード法の|V|回反復O(|V|^2|E|)より一般に早いことが期待される。（例えば、グラフに連結性を課せばワーシャルフロイド法が有利である）

負閉路が存在すると、最短距離は意味を持たない。しかし、ワーシャルフロイド法はその検出も行うことができる。

■アルゴリズムの正しさの証明：

〇負閉路が存在しない場合。本計算でkのforループm回目が終了したとき、dijが「頂点を{v1,...,vm,vi,vj}に制限した部分グラフにおけるviからvjへの最短距離（到達不能ならinfとする）」であることを示せばよい。mの帰納法による。

viからvjへの{v1..vm,vi,vj}上最短経路（重み和０の閉路の巡回を取り除くことで各頂点を高々１回しか通過しないとしてよい）は、存在すれば

・{v1..vm-1,vi,vj}上の最短路

・vi→...→vm→...→vjと二つの経路に分解出来て、vi→...→vmは{v1...vm-1,vi,vm}上の最短路、vm→...→vjは{v1...vm-1,vm,vj}上の最短路となる

のどちらかである。逆に、上の２つの経路がともに存在すれば、そのうち短い方がviからvjへの{v1..vm,vi,vj}上最短経路となることは明らかである。

 よって、その距離は(forループm-1回目終了直後のdに対して)min(dij,dim+dmj)となる。これはアルゴリズムが正しいことを示す。終了までdii=0なので、（やさしい）負閉路の検出はされない。

〇負閉路が存在する場合：負閉路を一つ取り、そこに含まれる最大添字の頂点をvqとする。これをvq→v<1>→…→v<p>→vqとしよう。<1>...<p>を昇順に並べると、<a1>...<ap>になるとする。forループが進むにつれて、k=<a1>,...,k=<ap>となる回がくる。

本計算の終了時にdqq<0となることを示したい。そのために、次のようなイメージを考えよう。閉路は円で、いま頂点たちがこの順で円上に並んでいる。頂点の間に、辺を表す矢印がある。以下は、p=4のときの図である。

f:id:nessinverse:20190115015114p:plain

k=<ai>のとき、v<ai>の両側にある２つの矢印は”縮約”される。

例を挙げる。a1=3,a2=1の場合を下の図で表示した。この図は、

f:id:nessinverse:20190115015504p:plain

・k=<3>のforループでd<2><4>≦d<2><3>+d<3><4>となったこと、

・その次にk=<1>のforループでdq<2>≦dq<1>+d<1><2>となったこと

を意味する。（つまり、矢印v<e>→v<f>とv<f>→v<g>が”縮約”することを、d<e><g>≦d<e><f>+d<f><g>が保証される、と言うことができる）

これを繰り返し、k=<ap>まで繰り返せば、p+1個の矢印は1個に縮約し、dqq≦(閉路の重みの和)となる。ところがこれは負だったので、証明が完了した。

 

２頂点間の最大フローを求めるのにも、ワーシャルフロイド法を応用できる。アルゴリズムの不等号の向きを逆転させ、加法をmin関数に置き換えることでよいことは容易にわかる。いつか他の記事で最大フロー問題を扱う。（きっと）

 

Johnson's algorithm

Johnson's algorithm（以下ジョンソン法）は、|E|が小さい（これをグラフが疎であるという）場合に特に、ワーシャルフロイド法よりも早くなりうるAPSPアルゴリズム。

 与えられたグラフをベルマンフォード法を用いて適切な非負重みグラフに変形し、ダイクストラ法を頂点個数分使うことで、時間計算量O(|V|^2log|V|+|V||E|)を実現する。|E|=|V|^2の最悪のケースでも、ワーシャルフロイド法と同等の計算量を実現する。

与えられたグラフG=(V,E)に対し、次のグラフG'=(V',E')を作る。
頂点V'=V∪{q}
辺　E'=E∪{ 辺qv | v∈V }、追加辺の重みは全て0

ベルマンフォード法でG'を始点=qとして探索する。頂点vへの最短距離をh(v)とする。
もし負経路が検出されれば、アルゴリズムを中止し負閉路の存在を出力する。

次のグラフG''=(V,E)を作る。
頂点、辺はGと同じ。辺uvの重みは、length(u,v)+h(u)-h(v)に変更する。

ダイクストラ法でG''を各頂点vに繰り返し適用し、APSPが解ける。
G''におけるuからvへの最短距離をdist(u,v)として、dist(u,v)+h(v)-h(u)をGにおける最短距離として出力する。

■証明：

〇負経路の検出：Ｇ’の定義より明らかに、Ｇ’における負経路はＧにおける負経路でもある。

〇辺の重みが非負になったこと：Ｇ’において、qからuへの最短経路に、辺uvをつけて作られるqからvへの路を考えれば、h(v)≦h(u)+length(u,v)が得られる。よって、length(u,v)+h(u)-h(v)≧0であり、ダイクストラ法が使える。

〇Ｇ''における最短距離が、Ｇにおける最短距離を与えること：Ｇ’’における経路v1→…→vnの重みは、length(v1,v2)+h(v1)-h(v2)+...+length(vn-1,vn)+h(vn-1)-h(vn)=length(v1,v2)+...+length(vn-1,vn)+h(v1)-h(vn)で与えられ、これはGにおける経路の重み+h(始点)-h(終点)である。よって、始点終点を固定したときに、最短経路はG、Ｇ’’において不変。そこで、dist(u,v)+h(v)-h(u)によってGにおける最短距離を得ることができる。

 

今日のまとめ

SSSP:ダイクストラ法(A*）が非負重みの場合、ベルマンフォード法が任意の場合。

APSP:ワーシャルフロイド法は実装が容易、ジョンソン法は一般にワーシャルフロイド法より高速なのが期待される。

 

ご清聴ありがとうございました。

*1:C++なら、<queue>ヘッダのstd::priority_queue<T>を用いるのが最も簡単である。