20. 네트워크 플로우
특정 지점에서 다른 지점으로 데이터를 흘러보내려고 할때(네트워킹), 가능한 모든 경로를 다 찾고, 흘러보낼 수 있는 최대의 유량을 계산하고 흘러보내는 알고리즘을 의미한다.
교통체증 및 네트워크 데이터 전송 등의 분야에서 활용가능한 알고리즘이다.
20-1. 데이터 이동
노드를 이어주는 간선정보에 데이터가 최대로 이동할 수 있는 용량과 현재 이동하는 데이터의 용량 정보가 입력된다.
각 간선에서 이동하는 데이터의 용량은 경로 상 최대로 이동할 수 있는 유량으로, 이동하는 경로 내 최대로 이동시킬 수 있는 유량을(간선들 중에 가장 작은 용량) 기준으로 데이터를 이동시킨다.
네트워크 플로우는 가능한 모든 경로를 탐색하고, 최대로 이동할 수 있는 유량(남아있는 용량만큼)을 흘려보내는 과정을 반복하는 알고리즘이다.
20-2. 에드몬드카프 알고리즘(BFS)
아래 graph에서 노드1부터 노드6까지 흘려보낼 수 있는 최대 유량을 계산해보자.
기본적으로 노드1부터 노드6까지 갈 수 있는 경로는 BFS를 이용하며, 에드몬드카프의 핵심은 탐색한 경로 상에서 이동시킬 수 있는 유량의 최대량을 도출한다.
모든 경우의 수를 탐색하기 위해 현재 흐르고 있는 유량을 0으로 설정, 가능한 용량(최대로 흘러보낼 수 있는 용량)을 탐색하는 과정을 반복적으로 더한다.
위 graph에서 에드몬드카프 알고리즘을 구현하기 위해, 노드1을 출발점 / 노드6을 도착지점으로 설정해서 갈 수 있는 모든 경로를 탐색해본다.
-
1>2>3>6
위 경로에서 흐를 수 있는 최대의 유량은 2>3의 용량인 6이다.
6의 유량이 흐른다면 각 간선유량은 6/12>6/6>6/8으로 업데이트된다. -
1>2>6
위 경로에서 1>2의 간선정보는 이미 6/12이고, 2>6의 간선정보는 0/9로 초기상태이다.
이때 최대로 흐를 수 있는 유량은 6이므로, 12/12>6/9의 간선정보로 업데이트된다.
간선정보가 누적되어있는 상태에서, 유량을 음수로 나타내서 새로운 경로와 유량정보를 업데이트할 수 있는 것이 에드몬드 카프 알고리즘의 핵심이다.
위 graph 간선 상 1>4>5>3>2>6으로 향하는 각 간선의 유량정보를 업데이트해보도록 한다.
최초 상태는 간선정보가 6/11>6/9>2/3>(3→2 양의 간선정보는 없는 상태)>6/9인 상태라 가정하자.
이때의 핵심은 유량정보가 음수가 될 수 있다는 점이다.
- 1>4>5>3>2>6
3에서 2로 향하는 경로정보는 없지만, 흐르는 유량에 대해 반대로 흐르는 음의 정보를 업데이트하게 되면 유량을 반대방향으로 옮길 수 있다.
이때 흘릴 수 있는 최대 유량은 1이므로 1만큼 유량을 누적시킨다(그 정보가 위와 같다).
이런 과정을 반복하면서 BFS로 경로를 진행할때 경로를 탐색하는 우선순위는 따로 존재하지 않고, 간선 내 남아있는 용량이 있다면 계속해서 흘려보낼 수 있는 유량을 구하고 누적하면 된다.
알고리즘이 모두 완료된 후, 출발점 노드1에서 최대로 흐를 수 있는 유량은 인접노드인 2와 4로 향하는 유량의 합이다(=19).
20-3. 시간복잡도
에드몬드카프 알고리즘의 시간복잡도는 인접노드의 간선 수 만큼 경로를 찾는 과정을 반복하므로, O(V*E^2)이다.
