Content deleted Content added
No edit summary |
→Improvement to Yen's improvement: new section |
||
Line 143:
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)
| |||