最短路さいたんろの基本きほん

1導入どうにゅう

この講義こうぎでは、辺数へんすうまたは辺重へんおもみの総和そうわを最小化さいしょうかする最短路問題さいたんろもんだいを定式化ていしきかし、BFS、ダイクストラ法ほう、負辺ふへんを扱あつかえる方法ほうほうの適用条件てきようじょうけんを説明せつめいする。

グラフの頂点ちょうてん・辺へん・歩道ほどう・道みちと、BFSの層構造そうこうぞうを前提ぜんていとする。

2グラフと経路けいろの定義ていぎ

有限ゆうげんグラフ $$G=(V,E)$$G=(V,E) を考かんがえる。無向むこうグラフでは辺へん $$\{u,v\}$$\{u,v\} に向むきがなく、有向ゆうこうグラフでは有向辺ゆうこうへん $$(u,v)$$(u,v) は $$u$$u から $$v$$v への移動いどうだけを許ゆるす。

$$s$$s から $$t$$t への歩道ほどうwalkとは、$$v_0=s,v_1,\dots ,v_k=t$$v_0=s,v_1,\ldots,v_k=t という頂点列ちょうてんれつであり、連続れんぞくする二頂点にちょうてんを結むすぶ辺へんが $$E$$E に属ぞくするものをいう。有向ゆうこうグラフでは辺へんの向むきも一致いっちしなければならない。頂点ちょうてんを反復はんぷくしない歩道ほどうを道みちpathと呼よぶ。辺数へんすうは $$k$$k である。

辺重へんおもみ関数かんすうedge-weight functionとは、各辺かくへんに実数じっすうを対応たいおうさせる関数かんすう $$w:E\to \mathbb{R}$$w:E\to\mathbb{R} である。歩道ほどう $$P=(v_0,\dots ,v_k)$$P=(v_0,\ldots,v_k) の費用ひようcostを

と定義ていぎする。無向辺むこうへんでは $$w(v_{i-1},v_i)$$w(v_{i-1},v_i) を、その二頂点にちょうてんを結むすぶ無向辺むこうへんの重おもみと解釈かいしゃくする。辺数へんすうを最小化さいしょうかする問題もんだいは、すべての辺へんに重おもみ $$1$$1 を与あたえた場合ばあいに一致いっちする。

3距離きょりと到達不能とうたつふのう

$$s$$s から $$t$$t への歩道ほどうの費用ひようの下限かげんを

と定義ていぎする。$$s$$s から $$t$$t へ到達不能とうたつふのうである場合ばあいは、候補こうほの集合しゅうごうが空くうであるため $$\delta (s,t)=+\mathrm{\infty }$$\delta(s,t)=+\infty とする。

閉歩道へいほどうclosed walkとは、始点してんと終点しゅうてんが一致いっちする歩道ほどうである。閉歩道へいほどうのうち、始点してん・終点しゅうてんを除のぞいて頂点ちょうてんを反復はんぷくせず、辺へんも反復はんぷくしないものを閉路へいろcycleと呼よぶ。有向ゆうこうグラフの負ふの閉歩道へいほどうは、その分解ぶんかいに負閉路ふへいろを少すくなくとも一ひとつ含ふくむ。

$$s$$s から到達可能とうたつかのうで、かつ $$t$$t へ到達可能とうたつかのうな負ふの閉歩道へいほどうが存在そんざいすると、その閉歩道へいほどうを任意回数にんいかいすうだけ反復はんぷくできる。この場合ばあいは $$\delta (s,t)=-\mathrm{\infty }$$\delta(s,t)=-\infty であり、最小費用さいしょうひようを達成たっせいする歩道ほどうは存在そんざいしない。無向むこうグラフでは、負辺ふへんを往復おうふくする閉歩道へいほどうの費用ひようが負ふになるため、その負辺ふへんを $$s$$s から $$t$$t への経路けいろに利用りようできるなら距離きょりは $$-\mathrm{\infty }$$-\infty である。

関連かんれんする負閉路ふへいろがなく、$$t$$t が到達可能とうたつかのうであるとする。任意にんいの $$s$$s から $$t$$t への歩道ほどうが頂点ちょうてんを反復はんぷくするなら、その間あいだの閉歩道へいほどうの費用ひようは非負ひふであり、これを除去じょきょしても費用ひようは増加ぞうかしない。この操作そうさを反復はんぷくすると道みちを得える。有限ゆうげんグラフの $$s$$s から $$t$$t への道みちは有限個ゆうげんこなので、その費用ひようの最小値さいしょうちを達成たっせいする道みちが存在そんざいする。この道みちを $$s$$s から $$t$$t への最短路さいたんろと呼よぶ。

4重おもみによる方法ほうほうの選択せんたく

4.1等ひとしい辺重へんおもみ

すべての辺重へんおもみが同おなじ正せいの定数ていすう $$c>0$$c>0 である場合ばあい、費用ひようは辺数へんすうの $$c$$c 倍ばいなので、費用ひようの最小化さいしょうかは辺数へんすうの最小化さいしょうかに一致いっちする。BFSは始点してんからの辺数へんすうが非減少ひげんしょうとなる順序じゅんじょで頂点ちょうてんを処理しょりするため、各到達可能頂点かくとうたつかのうちょうてんへの最短距離さいたんきょりを計算けいさんする。無重むおもみグラフは $$c=1$$c=1 と解釈かいしゃくする。

4.2非負ひふの辺重へんおもみ

すべての辺へんについて $$w\left(e\right)\ge 0$$w(e)\geq 0 である場合ばあい、ダイクストラ法ほうを適用てきようできる。この方法ほうほうは、暫定距離ざんていきょりが最小さいしょうの未確定頂点みかくていちょうてんを選択せんたくし、その頂点ちょうてんを経由けいゆする候補経路こうほけいろによって隣接頂点りんせつちょうてんの暫定距離ざんていきょりを更新こうしんする。非負性ひふせいにより、確定済かくていずみの距離きょりを後あとから短縮たんしゅくする経路けいろは存在そんざいしない。

4.3負辺ふへん

負辺ふへんnegative edgeとは $$w\left(e\right)<0$$w(e)<0 である辺へんをいう。負辺ふへんが一辺いっぺんでも存在そんざいすると、未確定頂点みかくていちょうてんを暫定距離ざんていきょりだけで確定かくていするダイクストラ法ほうの論拠ろんきょは成立せいりつしない。ただし、負辺ふへんの存在そんざいだけでは最短路さいたんろの不存在ふそんざいを意味いみしない。負閉路ふへいろが関連かんれんしない場合ばあいは、Bellman--Ford法ほうなど負辺ふへんを許容きょようする方法ほうほうを使用しようできる。

5最適部分構造さいてきぶぶんこうぞう

$$P=(v_0,\dots ,v_k)$$P=(v_0,\ldots,v_k) を $$v_0$$v_0 から $$v_k$$v_k への最短路さいたんろとする。$$0\le i<j\le k$$0\leq i<j\leq k に対たいし、部分道ぶぶんどう $$P[i:j]=(v_i,\dots ,v_j)$$P[i:j]=(v_i,\ldots,v_j) も $$v_i$$v_i から $$v_j$$v_j への最短路さいたんろである。これを最短路さいたんろの最適部分構造さいてきぶぶんこうぞうoptimal substructureと呼よぶ。

実際じっさい、$$P[i:j]$$P[i:j] より費用ひようの小ちいさい歩道ほどう $$Q$$Q が存在そんざいすると仮定かていする。$$P$$P の当該部分とうがいぶぶんを $$Q$$Q で置換ちかんすれば、$$v_0$$v_0 から $$v_k$$v_k への費用ひようが $$P$$P より小ちいさい歩道ほどうを構成こうせいでき、$$P$$P の最短性さいたんせいに矛盾むじゅんする。したがって主張しゅちょうが成立せいりつする。この性質せいしつは、緩和かんわによって部分問題ぶぶんもんだいの最良値さいりょうちを結合けつごうする最短路さいたんろアルゴリズムの基礎きそとなる。

6まとめ

• 無向むこう・有向ゆうこうの別べつと、歩道ほどう・道みちの別べつを明示めいじしてから最短路問題さいたんろもんだいを定式化ていしきかする。
• 到達不能とうたつふのうなら距離きょりは $$+\mathrm{\infty }$$+\infty であり、関連かんれんする負閉路ふへいろがあれば $$-\mathrm{\infty }$$-\infty である。
• 等重とうおもみではBFS、非負重ひふおもみではダイクストラ法ほうを適用てきようできる。負辺ふへんがある場合ばあいは別べつの方法ほうほうが必要ひつようである。
• 最短路さいたんろの任意にんいの部分道ぶぶんどうも、その両端りょうたんの間あいだの最短路さいたんろである。