Yenによる改良
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2018/04/10 17:11 UTC 版)
「ベルマン–フォード法」の記事における「Yenによる改良」の解説
1970年、Yenは負の重みがないグラフでのベルマン-フォード法の改良を発表した。Yenの改良は、まず全頂点に何らかの線型な順序を割り当て、全辺の集合を2つの部分集合に分割する。第1の部分集合 Ef は i < j となる全ての辺 (vi, vj) を含み、第2の部分集合 Eb は i > j となる辺 (vi, vj) を含む。そして頂点を v1, v2,...,v|V| の順に見ていき、その頂点から出ている Ef 内の辺を緩和させる。次に v|V|, v|V|-1,...,v1 という順序で頂点を見ていき、その頂点から出ている Eb 内の辺を緩和させる。Yenの改良は単一始点の最短経路問題で調べる必要のある経路数を事実上半減させる。
※この「Yenによる改良」の解説は、「ベルマン–フォード法」の解説の一部です。
「Yenによる改良」を含む「ベルマン–フォード法」の記事については、「ベルマン–フォード法」の概要を参照ください。
ウィキペディア小見出し辞書の「Yenによる改良」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- Yenによる改良のページへのリンク
