Content deleted Content added
fix bad counter |
|||
| (14 intermediate revisions by 10 users not shown) | |||
Line 1:
{{
{{WikiProject Mathematics|priority=Low}}
▲{{WikiProject Computer science|importance=mid|class=C}}
}}
{{User:MiszaBot/config
Line 14 ⟶ 13:
}}
{{Archive box|auto=yes}}
yeah can find a decent step by step guide to this on line. one that describes each detail of each step otherwise im not going to get it. <span style="font-size: smaller;" class="autosigned">— Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/84.203.48.54|84.203.48.54]] ([[User talk:84.203.48.54|talk]]) 19:53, 21 May 2013 (UTC)</span><!-- Template:Unsigned IP --> <!--Autosigned by SineBot-->▼
== 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 49 ⟶ 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.
▲
==Bellman–Ford algorithm in the informational description of the black hole==
Line 82 ⟶ 57:
[[User:Lothsahn|Lothsahn]] ([[User talk:Lothsahn|talk]]) 21:47, 31 October 2021 (UTC)
:Seems that the gif has been updated since then, but I still think it's not correct. On the frame that "t" changes from 6 to 2, shouldn't z change to -2 too instead of happening in the next frame? It suggests that z updates on the next loop after the t update one, but if I'm not mistaken it should be on the same frame since t changes to 2 and then after checking x and y, when it checks for z it should see that t is now -2 and not 6. Atleast that's what I understand should happen after reading the pseudocode. [[User:Marco2124|Marco2124]] ([[User talk:Marco2124|talk]]) 20:01, 7 December 2022 (UTC)
== New preprint ==
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:
▲
: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)
| |||