Talk:Bellman–Ford algorithm: Difference between revisions

Revision as of 02:14, 8 November 2023

Latest revision as of 01:13, 10 June 2024

(11 intermediate revisions by 8 users not shown)

Line 1:

{{VitalWikiProject articlebanner shell|class=C|levelvital=5yes|topic1=Mathematics}}

{{WikiProject Mathematics|priority=Low}}

{{WikiProjectBannerShell|

{{WikiProject Computer science|importance=mid|class=C}}

{{maths rating|class=B|priority=Low|field=discrete|rating=poor}}

{{WikiProject Computer science|importance=mid|class=C}}

}}

{{User:MiszaBot/config

Line 14 ⟶ 13:

}}

{{Archive box|auto=yes}}

== Pseudocode bug? ==

The pseudocode in the article states:

for i from 1 to size(vertices)-1:

I'm pretty sure that it's supposed to be

for i from 0 to size(vertices)-1:

or, equivalently

for i from 1 to size(vertices):

The program I made based on the pseudocode didn't work until I made this change. Can anyone confirm that this is indeed the case (and not just some other bug in my program) and if so, correct the article? --[[User:Smallhacker|Smallhacker]] ([[User talk:Smallhacker|talk]]) 15:38, 3 March 2011 (UTC)

One more clarification on the Pseudocode

for each edge (u, v) with weight w in edges:

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-->

==== proposed answer ====

Line 42 ⟶ 26:

the algorithm tries to relax all edges for every edge on the shortest path - followingly, only size(vertices) - 1 relax-iterations have to be computed.

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">—&nbsp;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 82 ⟶ 64:

Seems soon (after peer-review) there finally might be an improvement to this absolutely classical algorithm

https://arxiv.org/abs/2311.02520 [[Special:Contributions/2A00:20:5:B593:5C8F:D801:68C2:458|2A00:20:5:B593:5C8F:D801:68C2:458]] ([[User talk:2A00:20:5:B593:5C8F:D801:68C2:458|talk]]) 00:29, 8 November 2023 (UTC)

:Let's wait until it's at least been accepted to a conference before adding anything here. Anyway, the right place is [[Shortest path problem]], because it's a different algorithm than BF. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 05:02, 8 November 2023 (UTC)

== Pseudocode bug? ==

The pseudocode in the article states:

for i from 1 to size(vertices)-1:

I'm pretty sure that it's supposed to be

for i from 0 to size(vertices)-1:

or, equivalently

for i from 1 to size(vertices):

The program I made based on the pseudocode didn't work until I made this change. Can anyone confirm that this is indeed the case (and not just some other bug in my program) and if so, correct the article? --[[User:Smallhacker|Smallhacker]] ([[User talk:Smallhacker|talk]]) 15:38, 3 March 2011 (UTC)

One more clarification on the Pseudocode

for each edge (u, v) with weight w in edges:

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)