「ワーシャル–フロイド法」の版間の差分
削除された内容 追加された内容
m →メモリ管理 |
|||
19行目:
kをn以下の整数とし、K={1,...,k}とする。
Gの各頂点i,jに対し、GをK∪{i,j}に制限したグラフ上でのiからjへの最短経路をp<sub>i,j</sub>とする。(経路が無い場合はp<sub>i,j</sub>＝「なし」とする。)
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}内にあるかのいずれかであるので、
| |||