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

6.7

 全対最短経路

■

181

フロイド

-

ワーシャル法

Floyd-Warshall

最良 平均 最悪

O(V

3

)

allPairsShortestPath (G)

foreach u in V do

foreach v in V do

dist[u][v] =

∞

❶

最初は全節点が到達不能と考える。

pred[u][v] = -1

dist[u][u] = 0

foreach u

の隣接節点

v do

dist[u][v] =

辺

(u,v)

の重み

pred[u][v] = u

foreach k in V do

foreach u in V do

foreach v in V do

newLen = dist[u][k] + dist[k][v]

if newLen < dist[u][v] then

❷

s

から

v

へ、より短い経路が見つかったら、

新しい長さを記録する。

dist[u][v] = newLen

pred[u][v] = pred[k][v]

❸

新たに得られた

1

つ前のリンクを記録する。

end

6.7.2

 解

動的計画法方式では、より単純な部分問題の結果を順に計算する。

G

の辺を

まず考える。これらは、間に他の節点を含まない任意の

2

節点

u

と

v

の間の最短

経路長を表すものだ。行列

dist[u][v]

は、最初∞とセットされ、

dist[u][u]

は、

0

（節点

u

から自分自身への経路はコストがかからない）となる。そして、すべての辺

e

＝

(u, v)

∈

E

について、

dist[u][v]

がそ