최대 유량을 찾는 에드몬드 카프 알고리즘(Edmonds-Karp Algorithm) 배우기

1. 유량 네트워크(flow network) A에서 B까지 8명이 지나갈 수 있고, B에서 C까지 3명이 지나갈 수 있다고 해보자. A에서 C까지 1초가 걸린다고 한다면, A에서 B로 8명을 보낼때, 1초 후에 상황은 어떻게 될까 그러면 B에 5명이 대기하고 있고, C에는 3명이 도착해있다. 즉, A에서 B로 8명씩 보내는건 손해라는 의미 A에서 B로 8명씩 보낼 수 있지만, A에서 C까지 막힘없이 데이터를 전송할려면 1초에 3명씩 보내야한다는 소리이다. 위의 그림은 A에서 B로 최대 8명이 갈 수 있는데, 실제로는 3명이 흐르고 있다는 뜻 때때로 네트워크상 특정 지점에서 다른 지점으로 실제로 데이터가 얼마나 흐르고 있는가를 측정하는 것에 관심이 있다. 송유관에서 두 도시 사이 보낼 수 있는 석유의 양,..