fc2ブログ



最短経路

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 といいます。以下に例を示します。

SP.gif
スポンサーサイト



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

この記事へのコメント

コメントを書く


管理人にのみ表示

↑ページトップ

この記事へのトラックバック

この記事にトラックバックする(FC2ブログユーザー)

↑ページトップ