ダイクストラ法。非負の枝重みをもつグラフで、始点から各頂点への最短経路を、確定済み集合を広げながら貪欲に求めるアルゴリズム。とは？
意味
未確定頂点のうち距離最小のものを確定し、隣接頂点の距離を更新(緩和)する。優先度付きキューでO((E+V)logV)。負の重みには使えない。
?資格試験での問われ方
枝に非負の重みがある網で1点からの最短経路を求める算法は?
答え：ダイクストラ法。非負の枝重みをもつグラフで、始点から各頂点への最短経路を、確定済み集合を広げながら貪欲に求めるアルゴリズム。
✓覚え方
近い頂点から順に距離を確定
「ダイクストラ法。非負の枝重みをもつグラフで、始点から各頂点への最短経路を、確定済み集合を広げながら貪欲に求めるアルゴリズム。」を、演習で定着させる。
無料ではじめる →資格試験の過去問を、一問ごとの8-ways解説つきで。まずは無料で。
ukamiru 用語集 · 資格試験