麻省理工大学算法导论lecture18

《麻省理工大学算法导论lecture18》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture18Prof.ErikDemaineNegative-weightcyclesRecall:IfagraphG=(V,E)containsanegative-weightcycle,thensomeshortestpathsmaynotexist.Example:…<0uuvvBellman-Fordalgorithm:Findsallshortest-pathlengthsfromasource

2、s∈Vtoallv∈Vordeterminesthatanegative-weightcycleexists.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.2Bellman-Fordalgorithmd[s]←0foreachv∈V–{s}initializationdod[v]←∞fori←1to

3、V

4、–1doforeachedge(u,v)∈Edoifd[v]>d[u]+w(u,v)relaxationthend[v]←d[u]

5、+w(u,v)stepforeachedge(u,v)∈Edoifd[v]>d[u]+w(u,v)thenreportthatanegative-weightcycleexistsAttheend,d[v]=δ(s,v).Time=O(VE).©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.3ExampleofBellman-Ford∞ABCDE–1BB20∞∞∞∞0∞32AA1EE4–3CC5DD∞∞©2001byCharlesE.

6、LeisersonIntroductiontoAlgorithmsDay31L18.4ExampleofBellman-Ford–1∞ABCDE–1BB20∞∞∞∞0∞0–1∞∞∞32AA1EE4–3CC5DD∞∞©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.5ExampleofBellman-Ford–1∞ABCDE–1BB20∞∞∞∞0∞0–1∞∞∞32AA1EE0–14∞∞4–3CC5DD4∞©2001byCharlesE.L

7、eisersonIntroductiontoAlgorithmsDay31L18.6ExampleofBellman-Ford–1∞ABCDE–1BB20∞∞∞∞0∞0–1∞∞∞32AA1EE0–14∞∞4–30–12∞∞CC5DD42∞©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.7ExampleofBellman-Ford–1∞ABCDE–1BB20∞∞∞∞0∞0–1∞∞∞32AA1EE0–14∞∞4–30–12∞∞CC5DD2

8、∞©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.8ExampleofBellman-Ford–1∞ABCDE–1BB20∞∞∞∞010–1∞∞∞32AA1EE0–14∞∞4–30–12∞∞CC5DD0–12∞12∞©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.9ExampleofBellman-Ford–1∞ABCDE–1BB20∞∞∞∞010–1∞∞∞32AA1

9、EE0–14∞∞4–30–12∞∞CC5DD0–12∞12∞10–1211©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.10ExampleofBellman-Ford–1∞ABCDE–1BB20∞∞∞∞010–1∞∞∞32AA1EE0–14∞∞4–30–12∞∞CC5DD0–12∞12–210–12110–12–21©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.1

10、1ExampleofBellman-Ford–1∞ABCDE–1BB20∞∞∞∞010–1∞∞∞32AA1EE0–14∞∞4–30–12∞∞CC5DD0–12∞12–210–1211Note:Valuesdecrease0–12–21monotonically.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay31L18.12CorrectnessTheorem.IfG=(V,E)containsno