ベルマン–フォード法
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の改良は単一始点の最短経路問題で調べる必要のある経路数を事実上半減させる。