Talk:Edmonds–Karp algorithm: Difference between revisions

Revision as of 08:38, 11 March 2012

Latest revision as of 10:36, 29 September 2024

(12 intermediate revisions by 10 users not shown)

Line 1:

{{WikiProject banner shell|class=C|1=

{{maths rating

{{WikiProject Mathematics }}

|nested=

{{WikiProject Computing |importance=Low |science=yes |science-importance=Low |software=yes |software-importance=Low}}

|small=

}}

|class=start

|importance=low

|field=applied

|historical=

}}

{{WikiProject Computer science|importance=mid}}

==Discussion==

Line 68 ⟶ 63:

: I agree, and I think the Java and C are inappropriate for Wikipedia, which is not supposed to be a software library. [[User:Zero0000|Zero]]^{<small>[[User_talk:Zero0000|talk]]</small>} 19:35, 19 July 2011 (UTC)

: I disagree, it's refreshing to have the details of the algorithm presented. Many algorithms are sensitive to such details - the precise order in which "visited arrays" are updated, edge cases, etc. In this case, I recently improved the pseudocode to terminate once a shortest augmenting path from s to t is found. Without the details, other implementers may make the same mistake by iterating until the BFS queue is empty.

== Should BreadthFirstSearch take F as a parameter? ==

Line 79 ⟶ 76:

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)

==Push and pop==

The pseudocode uses "push" and "pop" for the queue handling. Push is fine, but pop (LIFO) will result in an algorithm that is extremely slow compared to shifting (FIFO). <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/94.255.217.210|94.255.217.210]] ([[User talk:94.255.217.210|talk]]) 21:16, 18 October 2012 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->

== External links modified ==

Hello fellow Wikipedians,

I have just modified one external link on [[Edmonds–Karp algorithm]]. Please take a moment to review [https://en.wikipedia.org/w/index.php?diff=prev&oldid=801065276 my edit]. If you have any questions, or need the bot to ignore the links, or the page altogether, please visit [[User:Cyberpower678/FaQs#InternetArchiveBot|this simple FaQ]] for additional information. I made the following changes:

*Added archive https://web.archive.org/web/20061005083406/http://www.cis.upenn.edu/~wilf/AlgComp3.html to http://www.cis.upenn.edu/~wilf/AlgComp3.html

When you have finished reviewing my changes, you may follow the instructions on the template below to fix any issues with the URLs.

{{sourcecheck|checked=false|needhelp=}}

Cheers.—[[User:InternetArchiveBot|'''<span style="color:darkgrey;font-family:monospace">InternetArchiveBot</span>''']] <span style="color:green;font-family:Rockwell">([[User talk:InternetArchiveBot|Report bug]])</span> 12:57, 17 September 2017 (UTC)

== Incorrect pseudo-code for the breadth-first-search part ==

It seems to me that the search can and should stop as soon as the sink node is reached. Indeed, all later processing is superfluous, as pred[t] can only be set once in each search.

As it is now, the search stops when the queue is empty. In the first pass, that happens only after all nodes reachable from the source have been visited.

[[User:JohannDeneux|JohannDeneux]] ([[User talk:JohannDeneux|talk]]) 15:45, 22 February 2020 (UTC)

I agree - each entry `pred[i]` is set exactly once, and set to the predecessor on the shortest path. So continuing the loop is completely unnecessary. I'll fix it soon. -- Anonymous <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/73.153.188.27|73.153.188.27]] ([[User talk:73.153.188.27#top|talk]]) 00:04, 6 September 2023 (UTC)</small> <!--Autosigned by SineBot-->

== Unnecessary Edge Update in the Pseudocode ==

The pseudocode mentions that each edge must have a back-flow variable, and updates the back-flow near the very end of the algorithm. But the back-flow values only ever set, they're not used in finding a next shortest augmenting path or its flow, or in computing the total flow. So they look unnecessary - like someone just copied from the earlier Ford-Fulkerson algorithm page. If it's not important to the algorithm then all references to back-flow in the pseudocode should be eliminated. -- Anonymous