Edmonds-karp Algorithm

개념

네트워크의 최대 유량을 구하는 알고리즘이다.

3가지 Network의 개념이 필요하다.

• Capacity Network : 노드간 가능한 최대 유량이 저장되는 Network이다.
• Flow Network : (알고리즘 수행중) 실제로 흐르는 유량이 저장되는 Network이다.
• Residual Network : 현재 더 흐를 수 있는 유량을 나타내는 Network이다.
  • 만약 어떤 Edge에 대하여 Capacity=3, Flow=2라면 더 흐를 수 있는 유량이 1이므로 Residual=1이다.

수행 과정

Edmonds-karp 알고리즘은 아래와 같이 진행된다.

1. Network의 구조를 입력받아 Capacity Network에 저장한다. 경로는 벡터등으로 Adjacency List 를 구현하여 따로 저장한다.
2. 아래의 과정을 더 흐를 수 있는 경로(Residual이 양수)가 존재하지 않을 때까지 반복한다.
   1. BFS를 통해 Source에서 Sink로 가는 경로를 구한다. 이때 Parent를 기록하면서 경로를 기억한다.
   2. 만약 Sink에 도달했다면 BFS를 종료한다.
   3. parent를 통해 저장했던 경로를 따라가면서 해당 경로에서 흐를 수 있는 최대 유량(경로중 Residual이 가장 작았던 유량)를 구한다.
   4. 이것이 흐르도록 처리한다. 해당 경로를 따라가면서 Flow Network에 구했던 최대유량을 더해준다. 여기서 경로의 반대 방향으로는 구해놨던 최대유량을 빼주어야 한다. 이미 흐른만큼 반대로 흐를수 있게 되었기 때문이다.
   5. 구해놨던 최대유량을 전체 Network의 최대유량에 더한다.

Resdidual Network를 따로 구현해도 되고 매순간 필요할때 Capacity - Flow로 사용해도 된다.

주의 사항

• Network의 입력값을 받을 때 양방향일 수도 있다. 이 경우 Capacity를 만들 때 양방향으로 넣어줘야 한다.
• 경로를 찾을 때 Capacity를 사용하면 시간이 오래걸린다. Adjacency List를 사용하여 검색해야 시간이 단축된다.

예시

백준 6086번 : 최대유량

6086번: 최대 유량