応用と一般化
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/07/03 19:37 UTC 版)
「ワーシャル–フロイド法」の記事における「応用と一般化」の解説
ワーシャル–フロイド法は以下のような問題を解くのに利用可能である: 有向グラフでの最短経路を求める（フロイドのアルゴリズム）。この場合、全エッジの重みを同じ正の値に設定する。通常、1 を設定するので、ある経路の重みはその経路上にあるエッジの数を表す。 有向グラフでの推移閉包を求める（ワーシャルのアルゴリズム）。スティーブン・ワーシャルの元々のアルゴリズムでは、重みなしのグラフであり、ブーリアンの隣接行列が使用されていた。そのため、加算の代わりに論理積(AND)が使われ、最小を求めるには論理和(OR)が使用されていた。 ある有限オートマトンにより受容される正規言語を記述する正規表現を探す（クリーネのアルゴリズム）。 実数の行列の逆行列を求める（Gauss-Jordan elimination）。 最適ルーティング。ネットワーク上の2つのノード間で通信量が最大な経路を求めるといった用途がある。そのためには上掲の擬似コードのように最小を求めるのではなく最大を求めるようにする。エッジの重みは通信量の上限を表す。経路の重みはボトルネックによって決まる。したがって上掲の擬似コードでの加算操作は最小を求める操作に置き換えられる。 無向グラフが2部グラフであるかどうかを確認する。
※この「応用と一般化」の解説は、「ワーシャル–フロイド法」の解説の一部です。
「応用と一般化」を含む「ワーシャル–フロイド法」の記事については、「ワーシャル–フロイド法」の概要を参照ください。
ウィキペディア小見出し辞書の「応用と一般化」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- 応用と一般化のページへのリンク
