많은 사람들이 Cormen 외 교수의 "알고리즘 소개"와 같은 판을 가지고 있지 않다고 생각하기 때문에 보조 정리 (및 내 질문)를 다음과 같이 작성합니다. 에드먼드 - 카프 알고리즘 명제 26.7 (3 판에서, 둘째로는 보조 정리 26.8 일 수있다) 다음 에드먼드 - 카프 알고리즘은 네트워크 흐름 G = (V, E)를 실행할 경우 소스 s 및 싱크 t에
Edmonds-Karp 알고리즘은 소스와 싱크 t 간의 최단 거리가 일 때 최단 경로가 증가 할 때마다 단조롭게 증가한다고 말합니다. 이 가정으로 소스 s와 싱크 t 사이의 거리는 | V |보다 크지 않을 것입니다. - 1. 나는 | V | 후에 소스 S와 싱크 T 사이에 더 이상 경로가 없다는 것을 의미한다고 생각한다. - 1 증강. 이것이 사실이라면 최
따라서 2 개의 가장 짧은 보강 경로 길이가 2 인 경우 보조 필터는 무엇입니까? 내가 아는 바로는 Edmonds-Karp가 최단 경로, 즉 가장자리가 가장 적은 경로를 선택합니다. 그러나이 두 경로 모두 길이가 2입니다. 그러면이 알고리즘이 확장되어 "최대/최소 흐름의 경로 선택"이라고 말합니까?