最短経路問題

shortest-path-problem.png

最短経路問題は、重みつき有効グラフG=(V,E,c)が与えられたとき、Vの2頂点間の距離とその距離を与える経路を求める問題であるが、
頂点の指定により以下のように分類される。

2頂点対最短経路問題 Vの2頂点s,tが与えられ、sとtの距離とその経路を求める
単一始点最短経路問題 Vの1頂点sが与えられ、sとtの距離とその経路を求める
全頂点対最短経路問題 Vのすべての2頂点間の距離とそれらの経路を求める

サポートサイト Wikidot.com