Loading [MathJax]/jax/output/CommonHTML/jax.js

본문 바로가기

Ford-Fulkerson Algorithm

(1)

139. Ford-Fulkerson Algorithm 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)은 일반적인 방향 그래프에서 최대 유량을 구하는 가장 간단한 알고리즘이다. 최대 유량은 일반적으로 소스에서 간선들을 따라서 싱크로 흘려보낼 수 있는 유량의 최댓값을 의미한다. 이 알고리즘은 다음과 같은 방법으로 작동한다. 1. 모든 간선의 유량을

$0$ 으로 초기화한다. 2. 소스에서 싱크로 데이터를 보낼 수 있는 경로를 찾는다. 이 경로를 증가 경로(Augmenting Path)라고 한다. 3. 증가 경로 중 더 보낼 수 있는 데이터의 양이 가장 작은 간선을 찾는다. 이 간선에 더 보낼 수 있는 데이터의 양을

$w$ 라고 하자. 4. 찾은 증가 경로를 통해

$w$ 의 데이터를 보낸다. 증가 경로에 포함된 모든 간선의 유량이

$w$ 만큼 증가하고..

티스토리툴바