最短経路
2006.04.26 22:53 グラフ 最短経路
Shortest path problem (最短経路問題) とは、重みつきグラフ G(V, E) において、ある与えられたノード x, y を接続する path の中で、エッジの重みの総和が最小である path を求める問題です。この問題には、様々な応用がありますが、以下の2つが重要です。
Single Source Shortest Path (SSSP) problem | |
グラフ G において、与えられた1つのノード s から、他の全てのノードへの最短経路を求める問題。 | |
All Pairs Shortest Path (APSP) problem | |
グラフ G において、全ての "ノードのペア" 間の最短経路を求める問題。 |
Single Source Shortest Path Problem (単一始点最短経路)
G(V, E) をエッジのコスト(長さ)が非負である重みつきグラフとし、s を、G のノードとします。ただし、s から G の全てのノードに対して経路があるものとします。このとき、s を根とし、s から G の全てのノードへの最短経路を包含する G の spanning tree T が存在します。このような tree を shortest path spanning tree といいます。以下に例を示します。

スポンサーサイト
| コメント(0) | トラックバック(0) | ↑ページトップ |