Edmonds-Karp 알고리즘의 복잡도

Question

Edmonds-Karp 알고리즘은 소스와 싱크 t 간의 최단 거리가 일 때 최단 경로가 증가 할 때마다 단조롭게 증가한다고 말합니다. 이 가정으로 소스 s와 싱크 t 사이의 거리는 | V |보다 크지 않을 것입니다. - 1. 나는 | V | 후에 소스 S와 싱크 T 사이에 더 이상 경로가 없다는 것을 의미한다고 생각한다. - 1 증강. 이것이 사실이라면 최대 유량을 찾는 복잡성은 (| V | - 1) * E가됩니다.

위의 내용을 잘못 가정합니다. 그러나 그것이 무엇인지 이해할 수 없었다. 누구든지 나를 도울 수 있습니까?

Answer 1

Introduction to Algorithms (아마도 초기 버전)에서 그들은 보조 정리 27.8에서 "단조롭게 증가한다"라고 말하지만, 실제로 그것이 증명하는 것은 모순이 있다는 것입니다. 그들이 정리 27.9에서이 보조 정리를 말하는 곳에서는 DELTAf (x, v) < = DELTAf '(S, v) 이후로 말합니다. 그래서 그들은 단조롭게 증가한다고 말하면서 "감소하지 않는다"또는 "증가하거나 남아 있습니다" 똑같다". 동일하게 유지 될 수 있다면 반복 횟수를 제한하는 데 사용할 수 없습니다.