「ワーシャル–フロイド法」の版間の差分
削除された内容 追加された内容
rv |
|||
22行目:
K'={1,...,k+1}とし、GをK'∪{i,j}に制限したグラフ上でのiからjへの最短経路をp'<sub>i,j</sub>とする。
K'∪{i,j}内でのiからjへの最短経路は、k+1を経由するか、あるいはK∪{i,j}内にあるかのいずれかであるので、
次が成立する事が分かる。ただしここで記号「p||q」はここで「経路pを進んだ後に経路qを進む」という経路を表す。
* p'<sub>i,j</sub> = p<sub>i,k+1</sub>||p<sub>k+1,j</sub> ：p<sub>i,k+1</sub>||p<sub>k+1,j</sub>がp<sub>i,j</sub>より短い場合
| |||