Dot Algo∙ DS/알고리즘 개념
2021. 12. 27.
[알고리즘] 네트워크 유량, 포드-폴커슨(Ford-Fulkerson) 알고리즘 (Java)
네트워크 유량 그래프 문제에는 경로의 길이 외에도 그래프에 대해 정의할 수 있는 중요한 개념이 있다. 바로 그래프의 ‘용량’이다. 각 간선이 용량을 갖는 그래프에서 두 정점 사이에 얼마나 많은 ‘흐름’ 혹은 ‘유량’을 보낼 수 있는지를 계산하는 문제를 네트워크 유량(network flow) 문제라고 부른다. 교통망에서 두 도시 사이를 이동할 수 있는 시간당 차량의 수, 송유관 네트워크에서 두 도시 사이에 보낼 수 있는 석유의 양 등 네트워크 유량은 현실에서 자주 찾을 수 있는 문제들이다. 또한 네트워크 유량은 굉장히 강력한 최적화 문제로, 그래프와 별 상관이 없어 보이는 다양한 최적화 문제들을 푸는 데도 이용할 수 있다. 유량 네트워크(flow network)란 각 간선에 용량(capacity)이라는 추..