maximumflow (2) 썸네일형 리스트형 디니츠의 알고리즘 (Dinitz' Algorithm) 지금까지 저는 제 블로그에서 최대 흐름 문제(maximum flow problem)를 많은 포스트를 통해서 다루어 왔습니다. 가장 최근에는 최대 흐름 문제를 다항 시간에 해결하는 에드몬즈-카프 알고리즘(Edmonds-Karp algorithm)을 소개해 드렸죠. 이번에는 에드몬즈-카프 알고리즘보다 더 빠른 시간에 최대 흐름 문제를 해결하는 방법 중 하나를 소개하고자 합니다. 바로 우리에게는 디닉의 알고리즘(Dinic's algorithm)으로 더 잘 알려진, 디니츠의 알고리즘(Dinitz' algorithm)입니다. 포탈에 검색해 봤더니 디니츠의 알고리즘을 어떻게 구현하는지 우리말로 설명한 게시글은 적잖이 볼 수 있었습니다. 다만 어째서 디니츠의 알고리즘이 에드몬즈-카프 알고리즘보다 효율적으로 동작하는지.. 에드몬즈-카프 알고리즘 (Edmonds-Karp Algorithm) 최대 흐름 문제(maximum flow problem)는 어떤 흐름 네트워크(flow network)가 주어졌을 때 시점(source)에서 종점(sink)까지 최대로 많은 양의 흐름을 찾는 문제입니다. 이때 흐름은 각 간선에서 용량(capacity)을 넘을 수 없고, 시점과 종점을 제외한 나머지 정점에서는 들어오는 양과 나가는 양이 동일해야 하죠. 지난 포스트에서는 이 문제를 풀기 위하여 잔여 네트워크(residual network)와 증가 경로(augmenting path)가 무엇인지에 대해서 살펴보았으며, 최종적으로는 매번 현재 흐름으로 정의되는 잔여 네트워크 위에서 시점에서 종점으로 향하는 임의의 증가 경로를 찾아 현재 흐름을 증가시켜 주면 (모든 간선의 용량이 유리수일 때) 언젠간 최대 흐름을 찾.. 이전 1 다음
