このページをはてなブックマークに追加このページを含むはてなブックマーク このページをlivedoor クリップに追加このページを含むlivedoor クリップ
  • 追加された行はこの色です。
  • 削除された行はこの色です。
  • 最短路問題 へ行く。

*目次 [#f8f420e4]

#contents


*最短路問題 [#ma478b87]

 グラフの枝には、属性として数値が与えられることがある。この数値のことを''重み(weight)''という。この重みは2点間のコストや長さなどを意味することが多い。

 グラフの2点間を結ぶ路のうちで、重みの総和が最小となる道順を求める問題を''最短路問題''という。これは、道路網における2点間の距離の最小値、ネットワークの通信網の回線選択方法など、応用範囲は広い。

 ここで考えるのは、重みの付いた有向グラフである。


*最短路問題のアルゴリズム [#p0dc60d2]

**ダイクストラ法 [#f11c17f9]

 ''ダイクストラ法(Dijkstra's algorithm)''は、最短路問題の代表的なアルゴリズムの一種である。基本的な考え方は、各点への最短路を出発点に近いところから、順次確定していく方法である。

 各辺に距離の付いた重み付きの有向グラフ上で任意の2点間の最短距離を求め、最終的にはすべての節への最短距離を求めるアルゴリズムである。始点から隣にある点を順次辿っていき、結果的に指定した出発の節から全部の節への最短距離が求められる。

[補講]ダイクストラ法を既知と仮定した問題が、基本情報やソフ開などの資格問題によく出題されている。

例:次のグラフにおいて、ダイクストラ法を使って、v1から各点への最短距離を求める。

#img(http://security2600.sakura.ne.jp/main2/image2/g3.jpg)
#img(,clear)

 ダイクストラ法で最短距離を求めるには、出発点からの最短距離のわかっている点の集合Sと、Sに含まれるいずれかの点に隣接する点の集合(Sの境界と呼ぶ)について最短距離に関する考察を加えながら、徐々にSに含まれる点を増やして、すべての点に対する最短距離を求めていく。

1:まずSには出発点であるv1だけが含まれているとして考察を進める。この場合、Sの境界はv2,v3,v4の3点がある。それぞれの距離は8,5,3である。この中の最短距離はv1→v4の3なので、v4を新たにSに含めることになる。

2:S={v1,v4}なので、Sの境界は{v2,v3}となる。SとSの境界の最短距離を考える(経由もあることに注意)。v1からのスタートしたときの直接の距離は8,5であるが、v4を経由すればv1→v4→v2(距離7=5+2)、v1→v4→v3(距離4=3+1)となる。この中の最短距離はv1→v4→v3の距離4である。よって、v3がSに加えられる。

3:S={v1,v3,v4}なので、Sの境界は{v2}となる。v2までの距離を求める。v1→v2(距離8)、v1→v3→v2(距離7)、v1→v4→v3→v2(距離6)なので、最短距離は6であり、「v1→v4→v3→v2」が最短距離となる経路になる。


*参考文献 [#eec600e1]

-『ソフトウェア開発技術者 合格エッセンシャルハンドブック』
-『ソフトウェア開発技術者試験対策 コンピュータサイエンス補足資料+午後演習問題』