Talk:Bellman–Ford algorithm: Difference between revisions

Revision as of 21:15, 7 August 2020

Latest revision as of 01:13, 10 June 2024

(26 intermediate revisions by 15 users not shown)

Line 1:

{{WikiProject banner shell|class=C|vital=yes|1=

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

{{WikiProject Computer scienceMathematics|importancepriority=mid|class=CLow}}

{{WikiProject Computer science|importance=mid}}

}}

{{User:MiszaBot/config

| algo=old(365d)

| archive=Talk:Bellman–Ford algorithm/Archive %(counter)d

| counter=31

| maxarchivesize=75K

| archiveheader={{Automatic archive navigator}}

Line 13 ⟶ 14:

{{Archive box|auto=yes}}

==== proposed answer ====

== RELAX?!?!? DON'T TELL ME TO RELAX WITHOUT DEFINING IT!!! ==

What a terrible, atrocious article, made all the worse by that fact that I cannot find a single decent explanation of it online (at least nowhere on the first page of Google results). This article doesn't explain the algorithm. It just puts a bunch of jargon up and walks away. You call that an explanation? Fuck you and the jargon-speaking horse you rode in on! How do I submit this article for deletion? [[Special:Contributions/98.180.51.94|98.180.51.94]] ([[User talk:98.180.51.94|talk]]) 23:14, 30 April 2013 (UTC)

for i from 1 to size(vertices) - 1

: Good job [https://en.wikipedia.org/w/index.php?title=Bellman%E2%80%93Ford_algorithm&diff=552968562&oldid=552967733 David Eppstein]! You seem like an awesome fellow! Hats off to you. :-) [[Special:Contributions/98.180.51.94|98.180.51.94]] ([[User talk:98.180.51.94|talk]]) 02:16, 1 May 2013 (UTC)

is correct.

in other other words: you intentionally leave one vertex out.

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

reason:

let a shortest path from '''s''' to an arbitrary vertex '''v''' contain ''k'' edges.

that means, the path ''p'' from s to v can be described as follows: ''p'' = ('''s''' = v₀, v₁, ..., v_k-1, v_k = '''v''').

in the worst case the shortest path visits all vertices of the graph. these are size(vertices). but the path between '''s''' and '''v''' only contains size(vertices) - 1 edges.

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.

yeahAs canfor findwhat a'''u''' decentis step by step guidesupposed to thisbe, on'''(u, line.v)''' oneis thatthe describesentire eachedge, detailstarting ofat eachvertex step'''u''' otherwiseand imfinishing notat goingvertex to get it'''v'''. <span style="font!--size Template:Unsigned smaller;"IP --><small class="autosigned">— &nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/84125.203239.4841.54100|84125.203239.4841.54100]] ([[User talk:84125.203239.4841.54100#top|talk]]) 1903:5346, 2124 MayNovember 20132023 (UTC)</span><!-- Template:Unsigned IP --small> <!--Autosigned by SineBot-->

==Reduction from an NP-Complete problem?==

==Bellman–Ford algorithm in the informational description of the black hole==

The lead cites a reduction by Sedgewick from the [[NP-Complete]] [[Hamiltonian path problem]] to the [[shortest path problem]]. Since the shortest path problem (even <ins>for all-pairs</ins> with <ins>edges of</ins> negative weight<del>s</del>) is not NP-Complete (i.e., Floyd-Warshall = O(n^3)), something needs to be clarified/corrected. <b>[[User:Justin W Smith|Justin W Smith]]</b> <i>^{[[User talk:Justin W Smith|talk]]}/_{[[Special:Contributions/Justin W Smith|stalk]]}</i> 06:15, 21 April 2010 (UTC)

: I think I figured out what was being said. If someone could verify this, I would appreciate it. <b>[[User:Justin W Smith|Justin W Smith]]</b> <i>^{[[User talk:Justin W Smith|talk]]}/_{[[Special:Contributions/Justin W Smith|stalk]]}</i> 14:08, 21 April 2010 (UTC)

Write the text.

The shortest (simple) path problem with arbitrary edge-weights is NP-hard. Moore-Bellman-Ford and Floyd-Warshall work only on graphs with conservative edge weights, i.e., there may be no cycles of negative total weight. In fact, MBF and FW compute a shortest walk with at most |V|-1 edges. In the case of conservative edge weights, these happen to be shortest (simple) paths. If there are negative cycles, this is not true. [[User:Morgurth|Morgurth]] ([[User talk:Morgurth|talk]]) 12:38, 1 November 2011 (UTC)

Does the shortest path of the informational chunks always result in a mixed state? We want that because a pure state will lead to informational loss. One other option is that informational loss exists, but isn't fundamental, because it is the result of untangling a more fundamental field, and dissipating that infoloss into the same spacetime field as virtual particles. <!-- Template:Unsigned IP --><small class="autosigned">—&nbsp;Preceding [[Wikipedia:Signatures|unsigned]] comment added by [[Special:Contributions/2A02:587:4118:7CA3:2891:994B:40B:F97D|2A02:587:4118:7CA3:2891:994B:40B:F97D]] ([[User talk:2A02:587:4118:7CA3:2891:994B:40B:F97D#top|talk]]) 21:15, 7 August 2020 (UTC)</small> <!--Autosigned by SineBot-->

:Whether this has anything real to do with shortest paths, or is just buzzword salad, I'm not sure, but it doesn't appear to have anything to do with this article, which is about a specific method for finding shortest paths and not on the general topic of shortest paths. And it also appears to be off-topic for this talk page, which is about improvements to the article based on published [[WP:RS|reliable sources]]. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 21:42, 7 August 2020 (UTC)

== Animated example ==

The animated gif in the article, while it is a very good initiative, seems to be either wrong or at least confusing.

First of all, what do the numbers next to the vertices mean? If they're the estimated distances, then iiuc they're not supposed to increase. But they do: v4 changes from 4 to 6 between frame #5 and frame #6, just as v3 does between frame #4 and frame #5.

Also, aren't there supposed to be 5 frames instead of 6? That is, the initial state plus the |V|-1 = 4 steps of the algorithm.

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

Line 41 ⟶ 81:

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

==== proposed answer ====

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)

for i from 1 to size(vertices) - 1

is correct.

:{{done}} —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 01:13, 10 June 2024 (UTC)

in other other words: you intentionally leave one vertex out.

reason:

let a shortest path from '''s''' to an arbitrary vertex '''v''' contain ''k'' edges.

that means, the path ''p'' from s to v can be described as follows: ''p'' = ('''s''' = v₀, v₁, ..., v_k-1, v_k = '''v''').

in the worst case the shortest path visits all vertices of the graph. these are size(vertices). but the path between '''s''' and '''v''' only contains size(vertices) - 1 edges.

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.

== Improvement to Yen's improvement ==

Re the "Yen's improvement" section of our article: an additional improvement by a factor of 2/3 may be obtained by choosing the linear ordering of the vertices randomly rather than arbitrarily. See {{citation|contribution=Randomized speedup of the Bellman–Ford algorithm|first1=M. J.|last1=Bannister|first2=D.|last2=Eppstein|author2-link=David Eppstein|arxiv=1111.5414|title=Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan|year=2012|pages=41–47|url=http://siam.omnibooksonline.com/2012ANALCO/data/papers/005.pdf}}. I'm leaving this note here rather than adding the reference myself because of the obvious conflict of interest. —[[User:David Eppstein|David Eppstein]] ([[User talk:David Eppstein|talk]]) 03:00, 10 December 2012 (UTC)

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

Write the text.