ダイクストラ法ほうの基本きほん

1導入どうにゅう

この講義こうぎでは、辺へんの重おもみが非負ひふであるグラフについて、ダイクストラ法ほうが単一始点最短距離たんいつしてんさいたんきょりを計算けいさんする方法ほうほうと、その正当性せいとうせいを説明せつめいする。暫定距離ざんていきょり、確定済かくていずみ頂点ちょうてん、緩和かんわを定義ていぎし、不変条件ふへんじょうけんとカット論法ろんぽうによって証明しょうめいする。

2問題設定もんだいせってい

有限ゆうげんの有向ゆうこうまたは無向むこうグラフ $$G=(V,E)$$G=(V,E)、始点してん $$s\in V$$s\in V、重おもみ関数かんすう $$w:E\to R_{\text{[PARSE ERROR: Undefined("Command("ge")")]}0}$$w:E\to\mathbb{R}_{\ge 0} を考かんがえる。道みちの長ながさを、その辺へんの重おもみの総和そうわとする。$$s$$s から $$v$$v への最短距離さいたんきょりを $$\delta (s,v)$$\delta(s,v) と表あらわし、到達不能とうたつふのうなら $$\delta (s,v)=\mathrm{\infty }$$\delta(s,v)=\infty とする。

3用語ようご

• 暫定距離ざんていきょり $$d\left[v\right]$$d[v] は、すでに発見はっけんした $$s$$s から $$v$$v への道みちのうち最小さいしょうの長ながさである。未発見みはっけんなら $$\mathrm{\infty }$$\infty とする。したがって、常つねに $$\delta (s,v)\text{[PARSE ERROR: Undefined("Command("le")")]}d\left[v\right]$$\delta(s,v)\le d[v] が成立せいりつする。
• 確定済かくていずみ集合しゅうごう $$S$$S は、$$d\left[v\right]=\delta (s,v)$$d[v]=\delta(s,v) であることを証明済しょうめいずみの頂点ちょうてんの集合しゅうごうである。この状態じょうたいを $$v$$v が 確定かくていした という。
• 緩和かんわ とは、辺へん $$(u,v)$$(u,v) に対たいして $$d\left[u\right]+w(u,v)<d\left[v\right]$$d[u]+w(u,v)<d[v] なら、$$d\left[v\right]\leftarrow d\left[u\right]+w(u,v)$$d[v]\leftarrow d[u]+w(u,v) と更新こうしんする操作そうさである。
• 優先度付ゆうせんどつきキュー は、未確定みかくていの候補こうほから $$d$$d が最小さいしょうの頂点ちょうてんを取とり出だすデータ構造こうぞうである。

4アルゴリズム

まず $$d\left[s\right]=0$$d[s]=0、$$v\ne s$$v\ne s に対たいして $$d\left[v\right]=\mathrm{\infty }$$d[v]=\infty、$$S=\text{[PARSE ERROR: Undefined("Command("varnothing")")]}$$S=\varnothing とする。優先度付ゆうせんどつきキューには $$(0,s)$$(0,s) を挿入そうにゅうする。その後ご、キューが空からになるまで次つぎを反復はんぷくする。

1. 距離値きょりちが最小さいしょうの組くみ $$(x,u)$$(x,u) を取とり出だす。
2. $$u\in S$$u\in S または $$x\ne d\left[u\right]$$x\ne d[u] なら、この古ふるい組くみを無視むしする。
3. それ以外いがいでは $$u$$u を $$S$$S に加くわえ、$$u$$u から出でる各辺かくへん $$(u,v)$$(u,v) のうち $$v\notin S$$v\notin S であるものを緩和かんわする。$$d\left[v\right]$$d[v] が減少げんしょうしたら、新あたらしい $$\left(d\right[v],v)$$(d[v],v) をキューに挿入そうにゅうする。

同おなじ頂点ちょうてんの古ふるい距離値きょりちがキューに残のこる実装じっそうでは、このような要素ようそを stale entry とよぶ。2 の検査けんさにより、decrease-key 操作そうさをもたないヒープでも正ただしく実装じっそうできる。

5不変条件ふへんじょうけん

各反復かくはんぷくの開始時かいしじに、次つぎが成立せいりつする。

1. $$u\in S$$u\in S なら $$d\left[u\right]=\delta (s,u)$$d[u]=\delta(s,u) である。
2. $$v\notin S$$v\notin S の $$d\left[v\right]$$d[v] は、$$s$$s から $$v$$v への道みちで、$$v$$v 以外いがいの頂点ちょうてんが $$S$$S に属ぞくするものの最小長さいしょうちょうである。$$v\ne s$$v\ne s では、内部頂点ないぶちょうてんが $$S$$S に属ぞくし、最後さいごの辺へんが $$S$$S から $$v$$v へ進すすむ候補こうほと同値どうちである。そのような道みちがなければ $$d\left[v\right]=\mathrm{\infty }$$d[v]=\infty である。

初期状態しょきじょうたいでは、$$s$$s への長ながさ 0 の道みちだけが候補こうほなので、この条件じょうけんが成立せいりつする。確定かくていした $$u$$u から出でる辺へんをすべて緩和かんわすると、$$S$$S を内部ないぶに使用しようして新あらたに到達とうたつできる候補こうほが過不足かぶそくなく反映はんえいされる。したがって 2 は保存ほぞんされる。

6確定操作かくていそうさの正当性せいとうせい

$$S$$S の外部がいぶで $$d$$d が最小さいしょうの頂点ちょうてんを $$u$$u とする。$$u=s$$u=s なら $$d\left[s\right]=0=\delta (s,s)$$d[s]=0=\delta(s,s) である。$$u\ne s$$u\ne s が始点してんから到達可能とうたつかのうであるとき、$$s$$s から $$u$$u への最短路さいたんろ $$P$$P を一ひとつ選えらぶ。$$P$$P が $$S$$S から $$V\setminus S$$V\setminus S へ最初さいしょに出でる辺へんを $$(y,z)$$(y,z) とする。この境界きょうかいを横断おうだんする議論ぎろんを カット論法ろんぽう という。

$$P$$P の $$s$$s から $$y$$y までの接頭部分せっとうぶぶんの長ながさを $$c\left(P\right[s:y\left]\right)$$c(P[s:y]) とする。$$y\in S$$y\in S なので、不変条件ふへんじょうけんと $$(y,z)$$(y,z) の緩和かんわから

重おもみがすべて非負ひふであるため、$$P$$P の $$z$$z 以降いこうを加くわえても長ながさは減少げんしょうせず、

が成立せいりつする。また $$u$$u の選択せんたくから $$d\left[u\right]\text{[PARSE ERROR: Undefined("Command("le")")]}d\left[z\right]$$d[u]\le d[z] であり、暫定距離ざんていきょりは実在じつざいする道みちの長ながさなので $$\delta (s,u)\text{[PARSE ERROR: Undefined("Command("le")")]}d\left[u\right]$$\delta(s,u)\le d[u] である。したがって、

となり、$$d\left[u\right]=\delta (s,u)$$d[u]=\delta(s,u) を得える。ゆえに $$u$$u を確定かくていしても不変条件ふへんじょうけん 1 は保存ほぞんされる。

7到達不能とうたつふのうな頂点ちょうてん

キューが空からになったとき、$$s$$s から到達可能とうたつかのうな頂点ちょうてんはすべて確定済かくていずみである。到達不能とうたつふのうな頂点ちょうてんはキューへ挿入そうにゅうされず、$$d\left[v\right]=\mathrm{\infty }$$d[v]=\infty のまま残のこる。無限大むげんだいの候補こうほを取とり出だして確定かくていする必要ひつようはない。

8負辺ふへんを許ゆるせない理由りゆう

$$s\to u$$s\to u の重おもみを 2、$$s\to v$$s\to v を 5、$$v\to u$$v\to u を -4 とする。ダイクストラ法ほうは $$d\left[u\right]=2$$d[u]=2 を $$d\left[v\right]=5$$d[v]=5 より先さきに確定かくていする。しかし、$$s\to v\to u$$s\to v\to u の長ながさは 1 であり、真しんの最短距離さいたんきょりは $$\delta (s,u)=1$$\delta(s,u)=1 である。負辺ふへんによってカットを横断おうだんした後あとに道みちの長ながさが減少げんしょうするため、証明しょうめいの非負性ひふせいを使用しようした不等式ふとうしきが破綻はたんする。

9計算量けいさんりょう

隣接りんせつリストと二分にぶんヒープを使用しようすると、有向辺ゆうこうへんは高々一度たかだかいちど緩和かんわされる。無向辺むこうへんは両端りょうたんの隣接りんせつリストに現あらわれるため、各方向かくほうこうから高々一度たかだかいちどずつ調査ちょうさされる。成功せいこうした緩和かんわごとに高々たかだか 1 個この組くみを挿入そうにゅうする。したがって、時間計算量じかんけいさんりょうは

であり、始点してんからすべての頂点ちょうてんへ到達可能とうたつかのうなら $$O\left(\right|E\left|\log \right|V\left|\right)$$O(|E|\log |V|) と表記ひょうきできる。stale entry を保持ほじする実装じっそうの補助空間ほじょくうかんは $$O\left(\right|V|+|E\left|\right)$$O(|V|+|E|) である。decrease-key を使用しようする実装じっそうでは、キューの要素数ようそすうを $$O\left(\right|V\left|\right)$$O(|V|) に抑おさえられる。

10要点ようてん

• ダイクストラ法ほうの前提ぜんていは、すべての辺重へんじゅうみが非負ひふであることである。
• 最小さいしょうの暫定距離ざんていきょりをもつ頂点ちょうてんを確定かくていできる根拠こんきょは、不変条件ふへんじょうけんとカット論法ろんぽうにある。
• stale entry、到達不能とうたつふのうな頂点ちょうてん、使用しようするヒープの操作そうさを実装仕様じっそうしようとして明示めいじする。