最短経路
与えられたグラフ
$ G(V, E)
の任意の
$ 2
頂点間の最短経路を求める問題。
すべての
$ 2
頂点間の最短経路を求めたい場合もあれば、特定の
$ 2
頂点間の最短経路を求めたい場合もあるし、あるいは特定の始点からすべての頂点への最短経路を求めたい場合もある。
用途や計算効率によって
ダイクストラ法
、
ワーシャル・フロイド法
、
ベルマン・フォード法
などを使って解く。