最短経路

Shortest path problem (最短経路問題) とは、重みつきグラフ G(V, E) において、ある与えられたノード x, y を接続する path の中で、エッジの重みの総和が最小である path を求める問題です。この問題には、様々な応用がありますが、以下の２つが重要です。

	Single Source Shortest Path (SSSP) problem
	グラフ G において、与えられた１つのノード 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 といいます。以下に例を示します。