search

williamfiset / Algorithms

A collection of algorithms and data structures
MIT License
16.84k stars 4.29k forks source link

Wrong complexity for Dinics #403

Open BlueskyFR opened 9 months ago

BlueskyFR commented 9 months ago

https://github.com/williamfiset/Algorithms/blob/da50861a53fc2f6642cfc7d82c285166f41d03e2/src/main/java/com/williamfiset/algorithms/graphtheory/networkflow/Dinics.java#L9C1-L9C1

Hey, I think the actual time complexity for Dinics algorithm is O(E^2V), not O(EV^2) as written.

Is the implementation non-optimal or is the comment simply wrong?