Content deleted Content added
Notification of altered sources needing review #IABot (v1.5.2) |
Assessment (Low): banner shell, Mathematics, +Computing, −Computer science (Rater) |
||
| (5 intermediate revisions by 4 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==
Line 66 ⟶ 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 101 ⟶ 100:
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
| |||