Talk:Bellman–Ford algorithm
 | This article has not yet been rated on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | |||||||||||||||||||||||||||||||||
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
Please add the quality rating to the {{WikiProject banner shell}} template instead of this project banner. See WP:PIQA for details.
| ||||||||||||||||||||||||||||||||||
| 1 |
|
This page has archives. Sections older than 365 days may be auto-archived by Lowercase sigmabot III if there are more than 5. |
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? 98.180.51.94 (talk) 23:14, 30 April 2013 (UTC)
- Good job David Eppstein! You seem like an awesome fellow! Hats off to you. :-) 98.180.51.94 (talk) 02:16, 1 May 2013 (UTC)
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. — Preceding unsigned comment added by 84.203.48.54 (talk) 19:53, 21 May 2013 (UTC)
Reduction from an NP-Complete problem?
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 for all-pairs with edges of negative weights) is not NP-Complete (i.e., Floyd-Warshall = O(n^3)), something needs to be clarified/corrected. Justin W Smith talk/stalk 06:15, 21 April 2010 (UTC)
- I think I figured out what was being said. If someone could verify this, I would appreciate it. Justin W Smith talk/stalk 14:08, 21 April 2010 (UTC)
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. Morgurth (talk) 12:38, 1 November 2011 (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? --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. — Preceding unsigned comment added by 49.203.64.216 (talk) 08:38, 25 May 2014 (UTC)
proposed answer
for i from 1 to size(vertices) - 1
is correct.
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 = v0, v1, ..., vk-1, vk = 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 Bannister, M. J.; Eppstein, D. (2012), "Randomized speedup of the Bellman–Ford algorithm", Analytic Algorithmics and Combinatorics (ANALCO12), Kyoto, Japan (PDF), pp. 41–47, arXiv:1111.5414. I'm leaving this note here rather than adding the reference myself because of the obvious conflict of interest. —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. 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. —David Eppstein (talk) 00:05, 3 April 2019 (UTC)
Bellman–Ford algorithm in the informational description of the black hole
Write the text.
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. — Preceding unsigned comment added by 2A02:587:4118:7CA3:2891:994B:40B:F97D (talk) 21:15, 7 August 2020 (UTC)
- 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 reliable sources. —David Eppstein (talk) 21:42, 7 August 2020 (UTC)