フロイド-ワーシャル法は、グラフ上のすべての頂点間の最短経路を効率的に求める動的計画法を用いたアルゴリズムです。負の重みを持つ辺があっても計算可能な点が特徴で、AIやネットワーク解析における様々な経路最適化問題の基礎として活用されています。
フロイド-ワーシャル法とは
フロイド-ワーシャル法とは、グラフ理論において、すべての頂点のペア同士の最短経路を一度に計算するためのアルゴリズムです。
詳しく解説
フロイド-ワーシャル法は動的計画法を応用したアルゴリズムであり、グラフ内のすべての頂点ペア間に存在する最短距離を求めることができます。計算量はO(V^3)（Vは頂点数）となり、頂点数が非常に多い大規模なグラフでは計算コストが高くなりますが、負の重みを持つ辺が存在する場合でも正しく動作するという優れた性質を持っています。AI分野では、知識グラフや状態遷移グラフにおける最短経路の探索、あるいはネットワーク分析などの前処理において重要な役割を担っています。
具体例・使われ方
AIにおける具体的な利用例として、知識グラフ上のエンティティ間における最短の論理的推論パスを見つける処理や、ロボティクスにおける状態空間グラフでの最適経路の導出などが挙げられます。また、通信ネットワーク上の最短ルーティング経路の計算にも応用されています。
似た用語との違い
ダイクストラ法が一つの始点から他のすべての頂点への最短経路を効率的に求める（単一始点最短経路問題）のに対し、フロイド-ワーシャル法はすべての頂点の組み合わせを同時に計算する（全点対最短経路問題）点が異なります。また、ダイクストラ法は負の重みを持つ辺を扱えませんが、フロイド-ワーシャル法は扱えるという違いがあります。
注意点
頂点数の三乗に比例して計算時間が増加するため、大規模なグラフデータに対して適用すると膨大な計算時間がかかる点に注意が必要です。また、グラフ内に負の閉路（合計の重みが負になるループ）が存在する場合は、最短経路が無限に小さくなってしまうため正しく計算できないという制限があります。