Edmonds-Karp Algorithm (1) 썸네일형 리스트형 140. Edmonds-Karp Algorithm 다음과 같은 그래프에서 포드-풀커슨 알고리즘으로 최대 유량을 구하는 경우를 생각해 보자. 포드-풀커슨 알고리즘은 증가 경로를 정하는 방법을 정의하지 않으므로, 운이 좋으면 증가 경로 $\text{S}$ - $\text{A}$ - $\text{T}$로 $10000$의 유량을 보내고 증가 경로 $\text{S}$ - $\text{B}$ - $\text{T}$로 $10000$의 유량을 보내서 두 번의 탐색으로 $20000$의 유량을 보낼 수 있다. 하지만 이 그래프에는 $\text{S}$ - $\text{A}$ - $\text{B}$ - $\text{T}$라는 증가 경로가 존재한다. 만약 이 경로를 선택할 경우 보낼 수 있는 유량은 $1$이고, 그러면 간선들의 유량은 다음과 같이 변한다. 이제 $\text{S.. 이전 1 다음
