Seonglae Cho 가중치가 있는 방향그래프(directed graph) G와 시작(source) 노드 s, 도착(sink) 노드 t가 주어졌을 때 각 엣지의 용량(capacity)을 고려하여 s에서 t로 흘려보낼 수 있는 최대 유량(flow)을 구하는 알고리즘을 가리킴
MFA Terms
최대 유량 알고리즘 (1)
이번 글에서는 최대 유량 알고리즘(Max Flow Algorithm) 을 포드-풀커슨 알고리즘(Ford-Fulkerson Algorithm)을 중심으로 살펴보도록 하겠습니다. 이 글은 고려대 김선욱 교수님과 역시 같은 대학의 김황남 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다. 최대 유량 알고리즘이란 가중치가 있는 방향그래프(directed graph) $G$와 시작(source) 노드 $s$, 도착(sink) 노드 $t$가 주어졌을 때 각 엣지의 용량(capacity)을 고려하여 $s$에서 $t$로 흘려보낼 수 있는 최대 유량(flow)을 구하는 알고리즘을 가리킵니다.
https://ratsgo.github.io/data%20structure&algorithm/2017/11/29/maxflow/
네트워크 플로우(network flow) & 포드 -풀커슨 &에드먼트-카프 알고리즘 (1)
문제 농사꾼 존은 소들이 충분한 물을 마시길 원했다. 그래서 농장에서 우물에서 외양간을 잇는 N개의 배수관의 지도를 만들기로 했다. 존은 아주 다양한 크기의 배수관들이 완전히 우연한 방법으로 연결돼있음을 알았다. 존은 파이프를 통과하는 유량을 계산하고 싶다. 두개의 배수관이 한줄로 연결 돼 있을 때 두 관의 유량 중 최소값으로 흐르게 된다.
https://m.blog.naver.com/PostView.nhn?blogId=jh20s&logNo=221298145631&proxyReferer=https%3A%2F%2Fwww.google.com%2F
