私たちの多くは、コーメン教授らの「アルゴリズム入門」と同じ版を持っていないと思うので、以下に補題 (および私の質問) を書きます。
Edmonds-Karp アルゴリズム
補題 26.7 (第 3 版では、第 2 版では補題 26.8 になる場合があります): ソース s とシンク t をもつフロー ネットワーク G=(V,E) で Edmonds-Karp アルゴリズムを実行すると、V{ s,t}、残差ネットワーク Gf の最短経路距離 df(s,v) は、各フロー拡張で単調に増加します。
証明: まず、V{s,t} のある頂点 v に対して、s から v への最短経路距離を減少させるフロー拡張があると仮定すると、矛盾が導き出されます。最短経路距離を減少させる最初の拡張の直前のフローを f とし、直後のフローを f' とします。df'(s,v) < df(s,v) となるように、拡張によって距離が減少した最小 df'(s,v) を持つ頂点を v とする。p = s ~~> u -> u を Gf' における s から v への最短経路とし、Ef' における (u,v) および
df'(s,u) = df'(s,v) - 1. (26.12)
v をどのように選択したかにより、ソース s から頂点 u までの距離が減少していないことがわかります。
df'(s,u) >= df(s,u)。(26.13)
...
私の質問は次のとおりです。私はそのフレーズをよく理解していません
" v をどのように選択したかにより、ソース s から頂点 u までの距離が減少しないことがわかります。つまり、df'(s,u) >= df(s,u) (26.13) "
v の選択方法は、「s から頂点 u までの距離が減少しない」という性質にどのように影響しますか? 式 (26.13) を導き出すにはどうすればよいですか。
u はパス (s,v) 上の頂点であり、(u,v) も (s,v) の一部です。(s,u) も減らないのはなぜですか?
ご協力ありがとうございました。