Content deleted Content added
this is all in CLRS |
m Open access bot: url-access=subscription updated in citation with #oabot. |
||
| (One intermediate revision by one other user not shown) | |||
Line 86:
== Proof of correctness ==
The correctness of the algorithm can be shown by [[mathematical induction|induction]]:<ref name="web.stanford.edu"/><ref>{{Cite journal |last=Dinitz |first=Yefim |last2=Itzhak |first2=Rotem |date=2017-01-01 |title=Hybrid Bellman–Ford–Dijkstra algorithm |url=https://www.sciencedirect.com/science/article/pii/S1570866717300011 |journal=Journal of Discrete Algorithms |volume=42 |pages=35–44 |doi=10.1016/j.jda.2017.01.001 |issn=1570-8667|url-access=subscription }}</ref>
'''Lemma'''. After ''i'' repetitions of ''for'' loop,
Line 214:
*{{Cite book|first1=Jørgen |last1=Bang-Jensen|first2=Gregory|last2=Gutin|year=2000|title=Digraphs: Theory, Algorithms and Applications|edition=First |isbn=978-1-84800-997-4|chapter=Section 2.3.4: The Bellman-Ford-Moore algorithm|publisher=Springer |url=http://www.cs.rhul.ac.uk/books/dbook/}}
*{{cite journal|first=Alexander|last=Schrijver|title=On the history of combinatorial optimization (till 1960)|pages=1–68|publisher=Elsevier|journal=Handbook of Discrete Optimization|year=2005|url=http://homepages.cwi.nl/~lex/files/histco.pdf}}
*{{sfn whitelist|CITEREFCormenLeisersonRivestStein2022}}{{Introduction to Algorithms|edition=4}} Section 22.1: The Bellman–Ford algorithm, pp. 612–616. Problem 22–1, p. 640.
*{{cite book | first1 = George T. | last1 = Heineman | first2 = Gary | last2 = Pollice | first3 = Stanley | last3 = Selkow | title= Algorithms in a Nutshell | publisher=[[O'Reilly Media]] | year=2008 | chapter=Chapter 6: Graph Algorithms | pages = 160–164 | isbn=978-0-596-51624-6 }}
*{{cite book|last1=Kleinberg|first1=Jon|author1-link=Jon Kleinberg|last2=Tardos|first2=Éva|author2-link=Éva Tardos|year=2006|title=Algorithm Design|___location=New York|publisher=Pearson Education, Inc.}}
| |||