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

6.7

 全対最短経路

■

179

6.7

 全対最短経路

単一始点から最短経路を探すのではなく、任意の節点対

(v

i

, v

j

)

の最短経路を求め

たいことがある。同じ距離を持つ複数の経路が存在することもある。この問題に対

する最速解は、

3

章で紹介した動的計画法

(dynamic programming)

を使うもので

ある。

動的計画法には、

2

つの興味深い特性がある。

●

小さな制約付きの問題を解き、その解を覚えておく。

●

問題に対する最適解を求めるのだが、解そのものよりも、最適解の値を計算

する方がやさしい。この例の場合では、節点対

(v

i

, v

j

)

に対して

v

i

から

v

j

への

最短経路の長さがまず計算できるが、その経路を得るには余分な計算を必要

とする、ということだ。次の疑似コードでは、

k, u, v

それぞれが

V

の可能な

節点を示す。

次に見る

フロイド

-

ワーシャル法

は、全節点対

(v

i

, v

j

)

に対して、

dist[i][j]

が

v

i

から

v

j

への最短経路の長さとなる、

n

×

n

行列

dist

を計算する。

図6-15は、図6-13と同じグラフでの

フロイド

-

ワーシャル法

の例を示す。計算し

た行列の第

1

行は図6-13のベクトルと同じだ。

フロイド

-

ワーシャル法

は、節点のす

べての対の最短経路を計算する。

6.7.1

 入出力

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

G

＝

(V, E)

。グラフの各辺

e

＝

(u, v)

には、正の（

0

よ

り大きい）重みが付随する。

フロイド

-

ワーシャル法

は、グラフの各節点

u

から（自分も含めて）全節点への最短

距離を要素として持つ行列

dist[][] ...