Ford Fulkerson (1) 썸네일형 리스트형 네트워크 플로우 Network Flow, 에드몬드-카프 Edmonds-Karp, 포드 풀커슨 Ford-Fulkerson 알고리즘 네트워크 플로우 Network Flow 특정 지점에서 다른 지점으로 데이터가 얼마나 많이 흐르고 있는지 측정하는 알고리즘 ⇒ 최대 유량 max flow 문제 해결에 사용되는 알고리즘 example A→D의 최대 유량은 6, 6 이상을 보내면 정체 현상이 발생하기 때문이다. 각 경로의 용량 중 가장 작은 것이 최대 유량 Terminologies flow: 두 정점 사이에서 현재 흐르는 양 capacity: 두 정점 사이에서 최대로 흐를 수 있는 양 source: 유량이 시작되는 정점 sink: 유량이 도착하는 정점 augumenting path: 소스에서 싱크로 유량을 보내는 경로 residual capacity: 용량 - 유량 Properties 용량 < 유량 (capacity < flow) flow(m.. 이전 1 다음
