[알고리즘] Maximum Flow : The Ford-Fulkerson method

(2021.11.23)

알고리즘 수업들으면서 정리하기 21탄

 

w12-2 녹강, w12-3 녹강, w13-1 실강

maximum flow, network flow 내용이다.

 

---

 

Flow network

 

 

 

 

 

Maximum-flow problem

: flow network G가 주어지고, source s, target t, capacity c 가 주어질 때,  value가 최대인 flow를 찾는 문제

 

몇가지 추가적인 정의들

 

 

Max-flow min-cut theorem

: max-flow의 값과 min-cut의 값이 같다.

 

 

 

 

 

The Ford-Fulkerson method

The Ford-Fulkerson method가  the maximum-flow problem을 해결한다.

input: a flow network G, source s, target t, capacity c

output: a flow whodse value is maximum

 

 

The Ford-Fulkerson method는 Residual networks를 사용한다.

> augmenting path를 찾으며 flow 값을 증가시킨다.

> residual network에 더이상 augemting path가 없을 때까지 flow 값을 증가시킨다.

 

 

 

Residual networks

 

> residual capacity 정의

 

 

 

 

 

 

 

 

 

 

 

진행 과정

 

 

value 값 확인

 

 

 

 

 

 

flow 값 없이 capacity만 나와있는 경우에서의 진행 상황

 

 

 

 

 

 

Performance of Ford-Fulkerson

finding augmenting path p: O(V+2E)=O(E) (by DFS, BFS)

total Ford-Fulkerson running time: O(E|f*|)