Content deleted Content added
m Signing comment by 130.237.222.140 - "" |
Assessment (Low): banner shell, Mathematics, +Computing, −Computer science (Rater) |
||
| (32 intermediate revisions by 21 users not shown) | |||
Line 1:
{{WikiProject banner shell|class=C|1=
{{WikiProject Mathematics }}
{{WikiProject Computing |importance=Low |science=yes |science-importance=Low |software=yes |software-importance=Low}}
▲ }}
==Discussion==
In the article, it is stated that "The distinguishing feature is that the shortest augmenting path is used at each step, which guarantees that the computation will terminate." However, as I understand it, the use of the shortest augmenting path ensure a faster running time than using breadth-running time. The terminiation of the computation is also ensured in the other algorithms based on Ford-Fulkerson, and has as such nothing to do with the breadth-first search.
I will try to work on this entry at a later stage.--[[User:Kristjan Wager|Kristjan Wager]] 09:52, 31 May 2005 (UTC)
Line 52 ⟶ 49:
At the end of the example it says that the minimal cut partitions the nodes into ''"sets {let A =6,B,C,E} and {D,F,G}, with the capacity c(A,D) + c(C,D) + c(E,G) = 3 + 1 + 1 = 5."'' But isn't the capacity here missing edge (D,E) with c(D,E) = 2 ? The capacity of the cut would then be 7 instead of 5. <small>—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/134.60.236.119|134.60.236.119]] ([[User talk:134.60.236.119|talk]]) 15:15, 23 October 2007 (UTC)</small><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
: No, the capacity is five. You should only count edges from the source set S to the sink set T. edge D,E is from T to S, and therefore does not increase the capacity. [[User:ArrowmanCoder|ArrowmanCoder]] ([[User talk:ArrowmanCoder|talk]]) 01:40, 20 February 2009 (UTC)
You state that "...and independently by Jack Edmonds and Richard Karp in 1972 (discovered earlier).". Well, that is usual in any science. Did anybody ask Dinic at what point in time he discovered the algorithm that is attributed to Edmonds and Karp? If not, then the remark "(discovered earlier)" should be removed. <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/130.237.222.140|130.237.222.140]] ([[User talk:130.237.222.140|talk]]) 14:52, 1 October 2008 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
== Minimum Cut ==
In the example can you explain why that's the minimum cut and how you find it? <span style="font-size: smaller;" class="autosigned">—Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/151.68.39.88|151.68.39.88]] ([[User talk:151.68.39.88|talk]]) 11:56, 8 February 2010 (UTC)</span><!-- Template:UnsignedIP --> <!--Autosigned by SineBot-->
== Pseudocode too detailed ==
I think this pseudocode is way too detailed. It is so detailed that it looks like an actually programming language. What do others think? [[User:Bender2k14|Bender2k14]] ([[User talk:Bender2k14|talk]]) 16:42, 19 July 2011 (UTC)
: 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]]<sup><small>[[User_talk:Zero0000|talk]]</small></sup> 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? ==
Or am I missing something?
Damix [[Special:Contributions/217.202.48.196|217.202.48.196]] ([[User talk:217.202.48.196|talk]]) 23:42, 10 September 2011 (UTC)
== Fatest pipe heuristic ==
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">— 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
| |||