Network flow (1) 썸네일형 리스트형 네트워크 유량 ( network flow) / 포드 - 풀커슨 알고리즘 JAVA network flow는 실세계에서 적용이 가능한 유명한 알고리즘이다. network flow를 이해하기 위해서는 먼저 몇가지 용어 정리가 필요하다. A -> B 로가는 네트워크에 대해서 최대 x라는 트래픽으로 보낼 수 있다면 capactiy(a,b) = x 가된다. 즉 a->b로 보낼 수 있는 최대 용량은 x라는 뜻이다. 만약 a->b에서 실제 y라는 트래픽이 발생한다면 flow(a,b) = y 가된다. 즉 a->b로가는 유량은 y라고 한다. 여기서 몇가지 속성을 알아보자 1. 용량 제한 속성 flow(u,v) 0 을 만족하는 u v 간선을 경로라고 생각하고 BFS 너비우선 탐색으로 경로를 탐색한다. 3. 만약 경로가 없으면 알고리즘은 종료한다. 4. 만약 경로가 존재한다면 경로에서 가장작은 flow .. 이전 1 다음
