반응형 [C++로 배우는 알고리즘과 자료구조 심화] Day 12: 네트워크 흐름 알고리즘 (Ford-Fulkerson, Edmonds-Karp) 네트워크 흐름 알고리즘네트워크 흐름 알고리즘은 유량 네트워크에서 최대 유량을 찾는 데 사용됩니다. 유량 네트워크는 용량이 지정된 방향성 그래프로, 네트워크의 한 정점에서 다른 정점으로 흐르는 유량을 나타냅니다. 오늘은 Ford-Fulkerson 알고리즘과 Edmonds-Karp 알고리즘에 대해 학습하겠습니다.Ford-Fulkerson 알고리즘Ford-Fulkerson 알고리즘은 증가 경로(augmenting path)를 반복적으로 찾아 최대 유량을 계산하는 알고리즘입니다. 이 알고리즘은 DFS를 사용하여 증가 경로를 찾습니다.Ford-Fulkerson 알고리즘의 시간 복잡도:최악의 경우: (O(E \times f)), 여기서 (E)는 간선의 수, (f)는 최대 유량입니다.Ford-Fulkerson 알고리.. 2024. 8. 1. 이전 1 다음 반응형
