Content deleted Content added
m Signing comment by 94.255.217.210 - "" |
Assessment (Low): banner shell, Mathematics, +Computing, −Computer science (Rater) |
||
| (8 intermediate revisions by 7 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==
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-->▼
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 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]]<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? ==
Line 87 ⟶ 84:
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
| |||