最初にウィキペディアから入手した、有名な円のベルマンフォード アルゴリズムの最適化に出くわしました。次に、演習セクションのいくつかの教科書で同じ改善を見つけました (たとえば、これは Cormen の問題 24-1 であり、Sedgewick の " Web 演習 N5 " です)。アルゴリズム」）。
改善点は次のとおりです。
Yen の 2 番目の改善では、最初にすべての頂点に任意の線形順序を割り当て、次にすべてのエッジのセットを 2 つのサブセットに分割します。最初のサブセット Ef には、i < j となるすべてのエッジ (vi、vj) が含まれます。2 番目の Eb には、i > j となるエッジ (vi、vj) が含まれます。各頂点は、v1、v2、...、v|V| の順序でアクセスされ、Ef のその頂点からの各出力エッジが緩和されます。次に、各頂点は v|V|、v|V|−1、...、v1 の順序で訪問され、Eb のその頂点からの各出力エッジが緩和されます。アルゴリズムのメイン ループの各反復では、最初のループの後に、少なくとも 2 つのエッジがエッジのセットに追加されます。エッジのセットには、緩和距離が正しい最短経路距離と一致します。1 つは Ef から、もう 1 つは Eb からです。この変更により、アルゴリズムのメイン ループの最悪の場合の反復回数が |V| から減少します。− 1 ～ |V|/2。
残念ながら、この束縛された |V|/2 の証明を見つけることができず、さらに、反例を見つけたようです。私はそれについて間違っていると確信していますが、どこが正確かわかりません。
反例は、1 から n までのラベルが付いた頂点と最初の頂点 1 を持つ単なるパス グラフです (つまり、1 から n-1 までの範囲の i に対して E={(i, i+1)})。その場合、前方頂点のセットは E (E_f = E) に等しく、後方頂点のセットは単なる空のセットです。アルゴリズムの反復ごとに、正しく計算された距離が 1 つだけ追加されるため、アルゴリズムは n-1 時間で終了します。これは、提案された制限 n/2 と矛盾します。
私は何を間違っていますか？
UPD:間違いは非常にばかげていました。パス コストの即時更新としての反復について考えて、頂点を介した反復は考慮しませんでした。この改善が誰かにとって興味深いものになる可能性がある場合に備えて、誰かが賛成票を投じたからといって、このトピックを削除するつもりはありません。