Ford-Fulkerson Algorithm (1) 썸네일형 리스트형 139. Ford-Fulkerson Algorithm 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)은 일반적인 방향 그래프에서 최대 유량을 구하는 가장 간단한 알고리즘이다. 최대 유량은 일반적으로 소스에서 간선들을 따라서 싱크로 흘려보낼 수 있는 유량의 최댓값을 의미한다. 이 알고리즘은 다음과 같은 방법으로 작동한다. 1. 모든 간선의 유량을 $0$으로 초기화한다. 2. 소스에서 싱크로 데이터를 보낼 수 있는 경로를 찾는다. 이 경로를 증가 경로(Augmenting Path)라고 한다. 3. 증가 경로 중 더 보낼 수 있는 데이터의 양이 가장 작은 간선을 찾는다. 이 간선에 더 보낼 수 있는 데이터의 양을 $w$라고 하자. 4. 찾은 증가 경로를 통해 $w$의 데이터를 보낸다. 증가 경로에 포함된 모든 간선의 유량이 $w$만큼 증가하고.. 이전 1 다음
