Ford Fulkerson Algorithm
※ 이 글은 개인 공부 글입니다. ※
출처 : https://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm
Ford–Fulkerson algorithm - Wikipedia
From Wikipedia, the free encyclopedia Jump to navigation Jump to search algorithm to compute the maximum flow in a flow network (equivalently; the minimum cut) The Ford–Fulkerson method or Ford–Fulkerson algorithm (FFA) is a greedy algorithm that computes
en.wikipedia.org
Ford Fulkerson Algorithm?
유량 네트워크(flow network)에서 최대 유량을 계산하는 Greedy 알고리즘.
유량?
단위 시간에 흐르는 액체의 양.. 으 .. 물리.. 으... 으.. 으..!!!!(물리 잘 못해요 ㅋ)
발신지(source)에서 출발한 흐름(flow)이 모든 간선에 존재하는 수용량(capacity)를 넘지 않고 끝 노드(sink)까지 도달하는 경로를 찾을 수 있다. 이들 경로중에 하나로 유량을 발생시키고 또 다른 경로를 찾는다. 이 과정을 반복할 때 가능한 수용량을 가진 경로를 augmenting path라 부른다.
augmenting path?
증대되는 경로 라는 뜻. V1,V2,V3...Vn를 경로로 갖는 경로가 존재할때 V1=s, Vn=t이고 Cf(Vi,Vi+1) > 0 을 만족하는 residual network에서 augmenting path가 존재한다.
flow network?
유향 그래프. 각각의 간선은 수용량을 갖고 유량을 받는다. 유량의 총량은 지나는 간선의 수용량을 넘을 수 없다.
어떤 노드로 진입하는 유량의 총량은 그것을 지나서 나가는 유량의 총량과 같다. 단, 발신지와 끝 노드(sink)는 이 조건을 만족하지 않는다.(발신지는 진입하는 유량이 없고, 끝 노드는 나가는 유량이 없으므로)
residual network?
유량이 지난것을 표시한 그래프.