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

170

■

6

章 グラフアルゴリズム

long newLen = dist[u];

newLen += ci->second;

if (newLen < dist[v]) {

pq.decreaseKey (v, newLen);

dist[v] = newLen;

pred[v] = u;

}

}

}

}

（個別の値はそうでなくとも）辺の重みの和が

numeric_limits<int>::max()

を超

えると算術エラーが生じる。エラーを避けるには、データ型

long

を用いて、

newLen

を計算する。

6.4.3

 分析

例6-3の

ダイクストラ法

の実装では、最初の優先度付きキューを構築するループ

は、挿入を

V

回行うので、性能は

O(V log V)

となる。次の

while

ループでは、各

辺が一度訪問され、

decreaseKey

が最大

E

回呼ばれるので、

O(E log V)

時間かかる。

全体性能は、

O((V

＋

E) log V)

となる。

6.5

 密グラフ用ダイクストラ法

隣接行列を使って表現した、密グラフに適した

ダイクストラ法

の別バージョン

がある。例6-4に示す

C

++

実装では、もはや優先度付きキューを使う必要がなく、

隣接行列を表す

2

次元行列を使うよう最適化している。これの性能は、

V

−

S

の

dist[]

の最小値がどれだけ速く取り出されるかによって決まる。まず

1

度に

1

つの

節点が

S

に足されるので、

while

ループは

V

回実行される。また、

V

−

S

の

dist[u]

の最小値を見つけるには、

V

節点すべてを調べる必要がある。 ...