アルゴリズムクイックリファレンス 第2版

168

■

6

章 グラフアルゴリズム

べる。例えば、

v

2

を処理した後で、このアルゴリズムは、

s

から

v

3

が、経路＜

s, v

2

,

v

3

＞によって距離

17

となることを見つける。

S

が

V

に等しくなるところまで大きく

なると、アルゴリズムは完了する。図6-12に最終結果を示す。

図6-12　ダイクストラ法は集合 S を拡張する

6.4.1

 入出力

入力は、有向重み付きグラフ

G

＝

(V, E)

および始点

s

∈

V

。各辺

e

＝

(u, v)

には、

非負重みが付随する。

ダイクストラ法

は、

2

つの配列を計算して生成する。主要結果は、始点

s

からグラ

フの各節点への最小距離を表す値の配列

dist[]

である。第

2

の結果は、始点

s

から

グラフの各節点に至る実際の最短経路の再計算に使われる配列

pred[]

である。

辺の重みは非負（

0

以上）である。この仮定が成り立たないなら、

dist[]

は不正な

結果を含んでしまう。より問題なのは、すべての重みの和が

0

より小さい閉路が存

在するなら、

ダイクストラ法

は永遠にループする可能性があることだ。

6.4.2

 解

ダイクストラ法

の実行中、

dist[v]

は、集合

S

内の訪問済み節点のみを経由すると

きの

s

から

v

への最短経路の長さの最大値を表す

＊

1

。各

v

∈

S

に対して、

dist[v]

は解

＊1 訳注：ここの概念はややわかりにくい。

dist[v]

は

v

∈

V

-

S

に対しては最短距離の候補を表しているの

みで、より短い距離が発見されると書き換えられる。例えば図6-11 で最初

dist[3]

は∞だが、これは

s

から

v

への最短距離が ...