ワーシャル–フロイド法

ウィキペディア

ワーシャル–フロイド法

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2023/11/16 14:20 UTC 版)

最短経路問題 > ワーシャル–フロイド法

ワーシャル–フロイド法（英: Floyd–Warshall Algorithm）は、重み付き有向グラフの全ペアの最短経路問題を多項式時間で解くアルゴリズムである。名称は考案者であるスティーブン・ワーシャル（英語版）とロバート・フロイドにちなむ（2人はそれぞれ独立に考案）。フロイドのアルゴリズム、ワーシャルのアルゴリズム、フロイド–ワーシャル法とも呼ばれる。

概要

ワーシャル–フロイド法の概略は以下の通りである：

• 入力：
  • (有向または無向)グラフ ${\displaystyle G=(V,E)}$
    Optimization computes maxima and minima.

非線形(制約付き)

一般	バリア関数 ペナルティ関数法（英語版）
微分可能	ラグランジュの未定乗数法 逐次二次計画法 連続線形計画（英語版）

凸最適化

凸縮小化	切除平面法（英語版、デンマーク語版、ドイツ語版、スペイン語版） 簡約勾配法 劣勾配法（英語版）
線型 および 二次	内点法 カチヤン楕円体法 カーマーカーの投影アルゴリズム ベイズ-交換 単体法 改訂シンプレックス法（英語版） 十字法（英語版） レムケの主ピボット操作法（英語版）

組合せ最適化

系列範例 (Paradigms)	近似アルゴリズム 動的計画法 貪欲法 整数計画問題(分枝限定法 若しくは 切断)
グラフ理論	最小全域木 ベルマン–フォード法 ブルーフカ法 ダイクストラ法 ワーシャル–フロイド法 ジョンソン法（英語版） クラスカル法 最大フロー問題 Dinic法（英語版） エドモンズ・カープ フォード・ファルカーソン プッシュリラベル最大流アルゴリズム（英語版）

メタヒューリスティクス

• 進化的アルゴリズム（進化戦略）
• 山登り法
• 局所探索法
• 焼きなまし法
• タブーサーチ
• ベイスンホッピング法

• カテゴリ（最適化 • アルゴリズム） • ソフトウェア（英語版）