最短経路問題

最短経路問題

ある点からある点へ到達する最短の経路を求める問題

ベルマン-フォード法、ダイクストラ法(OSPFで使われている)、A*などがある。

A*はヒューリスティック関数(この場合、最短経路の推定値を求める関数)を使用してダイクストラ法を改良したもの。


閉路の場合、NP困難である巡回セールスマン問題がよく知られる。