「ワーシャル–フロイド法」の版間の差分

'''ワーシャル-フロイド法'''（{{lang-en-short|Warshall-Floyd Algorithm}}）は、重み付き有向[[グラフ理論|グラフ]]の全ペアの[[最短経路問題]]を[[多項式時間]]で解く[[アルゴリズム]]である。名称は考案者である{{仮リンク|スティーブン・ワーシャル|en|Stephen Warshall}}と[[ロバート・フロイド]]に因む（二人はそれぞれ独立に考案）。'''フロイドのアルゴリズム'''、'''ワーシャルのアルゴリズム'''、'''フロイド-ワーシャル法'''とも呼ばれる。

* 有向グラフでの[[推移閉包]]を求める（ワーシャルのアルゴリズム）。[[スティーブン・ワーシャル]]の元々のアルゴリズムでは、重み無しのグラフであり、[[ブーリアン]]の隣接行列が使用されていた。そのため、加算の代わりに[[論理積]](AND)が使われ、最小を求めるには[[論理和]](OR)が使用されていた。