Content deleted Content added
Fixed {{Vital article}}; WP:TALKORDER |
|||
| (16 intermediate revisions by 12 users not shown) | |||
Line 1:
{{
{{WikiProject Mathematics|priority=Low}}
▲{{WikiProject Computer science|importance=mid|class=C}}
}}
{{User:MiszaBot/config
| algo=old(365d)
| archive=Talk:Bellman–Ford algorithm/Archive %(counter)d
| counter=
| maxarchivesize=75K
| archiveheader={{Automatic archive navigator}}
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 69 ⟶ 44:
And what do the thick arrows and grey vertices mean? Are they the vertices we already have the final distances of, and the shortest paths leading to them? The problem with this is that the algorithm is not supposed to "know" these at that point - if we stop there, we cannot be sure that we would not get better results (shorter paths) for these vertices in a later step.
==== Thoughts by another editor ====
I agree with the confusion. I believe that v3 and v4 incorrectly update. There is no possible path by which the cost to v4 is 4, so there's no way the algorithm should ever update the weight to 4. And like the parent said, the algorithm should never increase the weight, so v3 shouldn't temporarily change to 6 and back to 4. I think the original creator of the gif simply swapped the two values by accident.
It also converges after 3 cycles, which is common for this algorithm. In fact, this algorithm can converge after 1 cycle, if the optimal path is (randomly) selected.
I think removing the bold edges, darkening of the vertexes, and stopping the animation after the 3rd frame would really help this page, but I didn't make the change in case I misunderstand the algorithm.
P.S. First comment. Please don't bite the newcomer. I couldn't find a way to comment on the original post so I added to it.
[[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)
| |||