Talk:Bellman–Ford algorithm: Difference between revisions

Browse history interactively

← Previous edit

Content deleted Content added

VisualWikitext

Add topic

Revision as of 05:29, 9 January 2024 edit Cewbot (talk \| contribs) Bots 8,374,018 edits m Maintain {{WPBS}} and vital articles: 2 WikiProject templates. Merge {{VA}} into {{WPBS}}. Keep majority rating "C" in {{WPBS}}. Keep 1 different rating in {{Maths rating}}. Remove 1 same rating as {{WPBS}} in {{WikiProject Computer science}}. ← Previous edit		Latest revision as of 01:13, 10 June 2024 edit undo David Eppstein (talk \| contribs) Autopatrolled, Administrators 235,646 edits →Proposed Merger: SPFA into Optimizations: Reply Tag: Reply
(5 intermediate revisions by 5 users not shown)
Line 1: {{WikiProject banner shell\|class=C\|vital=yes\|1= {{WikiProject Mathematics~~\|class=B~~\|priority=Low~~\|field=discrete\|rating=poor~~}} {{WikiProject Computer science\|importance=mid}} }} Line 27: As for what '''u''' is supposed to be, '''(u, v)''' is the entire edge, starting at vertex '''u''' and finishing at vertex '''v'''. <!-- Template:Unsigned IP --><small class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/125.239.41.100\|125.239.41.100]] ([[User talk:125.239.41.100#top\|talk]]) 03:46, 24 November 2023 (UTC)</small> <!--Autosigned by SineBot--> ~~== Pop up shortest-path figure ==~~ The "shortest path" link in the first sentence pops up a figure whose caption refers to edge weights, yet the figure doesn't show any. [[User:Mdmi\|Mdmi]] ([[User talk:Mdmi\|talk]]) 21:25, 2 April 2019 (UTC) :That is an issue with the [[shortest path problem]] article, not with this article. The pop-up always picks the first image in the article, and the first image of that article was not a particularly useful one. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 00:05, 3 April 2019 (UTC) ==Bellman–Ford algorithm in the informational description of the black hole== Line 86 ⟶ 82: in this line what is u ? I beleive u should be changed to i or vice versa. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures\|unsigned]] comment added by [[Special:Contributions/49.203.64.216\|49.203.64.216]] ([[User talk:49.203.64.216\|talk]]) 08:38, 25 May 2014 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot--> :If there are n vertices, the algorithm needs to iterate n-1 times (as in the given pseudocode), not n times (as your change would have it). It starts out with one vertex having the correct distance (the starting vertex) and each iteration adds one more, so only n-1 iterations are needed until all are correct. If you implemented it correctly the nth iteration would be useless. Further, the case where exactly n-1 iterations are necessary should be unusual: it only happens when the shortest path runs through all vertices and the order of relaxation within an iteration is backwards for the edges of this path. So I strongly suspect it is some other bug in your program. —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 08:20, 24 November 2023 (UTC) == Proposed Merger: [[SPFA]] into Optimizations == Pretty much all in the title. The Moore Optimization has a whole article, which takes its name after that in the Fanding Duan article (1994) which popularized it in China. The relevance of having a whole article for it, since its worst case is the same as Bellman-Ford, does not seem to meet the standard. [[User:Wyrdwritere\|Wyrdwritere]] ([[User talk:Wyrdwritere\|talk]]) 03:51, 7 April 2024 (UTC) :{{done}} —[[User:David Eppstein\|David Eppstein]] ([[User talk:David Eppstein\|talk]]) 01:13, 10 June 2024 (UTC)