エドモンズ・カープのアルゴリズム
(エドモンズ・カープ法 から転送)
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/03/03 09:55 UTC 版)
エドモンズ・カープのアルゴリズム(英: Edmonds-Karp algorithm)は、フローネットワークの最大フロー問題を解くフォード・ファルカーソンのアルゴリズムの実装の一種であり、
各辺にある
このアルゴリズムで発見する増加道(赤で示されている)の長さが決して減少しない点に注意されたい。発見した道は、その時点の最短である。見つかったフローは、グラフの始点と終点を分離するように横切る最小カットをまたぐ容量と等価である。このグラフには最小カットは1つしかなく、
一般 | |
---|---|
微分可能 |
凸縮小化 | |||||||
---|---|---|---|---|---|---|---|
線型 および 二次 |
|
系列範例 (Paradigms) |
|||||
---|---|---|---|---|---|
グラフ理論 |
|
||||
ネットワークフロー (最大流問題) |
|
エドモンズ・カープのアルゴリズムと同じ種類の言葉
アルゴリズムに関連する言葉 | グローバーのアルゴリズム 分割アルゴリズム(ぶんかつあるごりずむ) RCアルゴリズム BCJRアルゴリズム エドモンズカープのアルゴリズム |
- エドモンズ・カープのアルゴリズムのページへのリンク