Flow network - 네트워크 플로우
실현 가능한 유량부터 잔여 간선의 증가와 취소, 컷의 상한, 포드–풀커슨 알고리즘의 종료 조건까지 살펴봅니다.
카테고리
Graph theory
3 articles.
2022-04-12
Floyd-Warshall Algorithm - 플로이드 워셜 알고리즘
플로이드–워셜의 모든 쌍 최단 경로 점화식을 유도하고, 안전한 C++ 구현과 도달 불가·음수 사이클의 의미를 살펴봅니다.
Max-flow min-cut theorem - 최대 유량 최소 컷 정리
잔여 네트워크의 도달 가능성을 이용해 최대 유량 최소 컷 정리를 증명하고, 작은 예제로 최적성을 확인합니다.