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

6.4

 単一始点最短経路

■

165

幅優先探索

Breadth-First Search

最良 平均 最悪

O(V

＋

E )

breadthFirstSearch (G, s)

foreach v in V do

pred[v] = -1

dist[v] =

∞

color[v] = White

❶

最初はすべての節点が未訪問の白である。

color[s] = Gray

dist[s] = 0

Q = empty Queue

❷

訪問した灰色の節点の集まりをキューに保持する。

enqueue (Q, s)

while Q

空でない

do

u = head(Q)

foreach u

の隣接節点

v do

if color[v] = White then

dist[v] = dist[u] + 1

pred[v] = u

color[v] = Gray

enqueue (Q, v)

dequeue (Q)

color[u] = Black

❸

すべての隣接点を訪問したら、この節点は完了。

end

6.4

 単一始点最短経路

ヴァーモント州のサンジョンズベリー（

Saint Johnsbury

）からテキサス州のウェ

イコ（

Waco

）に自家用飛行機で最短経路を行きたいとしよう。また、各空港間の距

離がわかっているとする。この問題を解くアルゴリズムで一番よく知られているの

は

ダイクストラ法

（

Dijkstra's algorithm

）

＊

1

である。これによって、サンジョンズベ

リーから他のすべての空港への最短経 ...