Content deleted Content added
No edit summary |
→Edge weights must be: non-zero? positive?: new section |
||
Line 79:
Edmonds Karp is sometimes implemented using fatest path instead of shortest path. This has a runtime of O(|E|^2*logC) with C being the max flow. (for sparse graphs it's O(|E|logC*(|E|+|V|log|V|)) using Dijkstra).
I guess |V| rarely much larger than logC, but perhaps the variation should be mentioned for completeness? <small><span class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[User:Thomasda|Thomasda]] ([[User talk:Thomasda|talk]] • [[Special:Contributions/Thomasda|contribs]]) 00:12, 28 February 2012 (UTC)</span></small><!-- Template:Unsigned --> <!--Autosigned by SineBot-->
== Edge weights must be: non-zero? positive? ==
Will this algorithm work correctly for edge weights of zero? If so, will the result always, sometimes, or never include those edges in the min-cut?
Will the algorithm work correctly if edge weights are negative?
Thanks,[[Special:Contributions/128.112.139.195|128.112.139.195]] ([[User talk:128.112.139.195|talk]]) 21:28, 16 July 2012 (UTC)
| |||