资源描述：
《lecture 18 shortest paths ii bellman-ford, linear programming, difference constraints》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、MITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Pleaseusethefollowingcitationformat:ErikDemaineandCharlesLeiserson,6.046JIntroductiontoAlgorithms,Fall2005.(MassachusettsInstituteofTechnology:MITOpenCourseWare).http://ocw.mit.edu(accessedMMDD,YYYY).License:
2、CreativeCommonsAttribution-Noncommercial-ShareAlike.Note:Pleaseusetheactualdateyouaccessedthismaterialinyourcitation.FormoreinformationaboutcitingthesematerialsorourTermsofUse,visit:http://ocw.mit.edu/termsMITOpenCourseWarehttp://ocw.mit.edu6.046JIntroductiontoAlgorithms,Fall2005Tr
3、anscript–Lecture18Goodmorning,everyone.Gladyouareallherebrightandearly.I'mcountingthedaystilltheTA'soutnumberthestudents.They'llshowup.Wereturntoafamiliarstory.Thisisparttwo,theEmpireStrikesBack.Solasttime,ouradversary,thegraph,cametouswithaproblem.Wehaveasource,andwehadadirectedgr
4、aph,andwehadweightsontheedges,andtheywereallnonnegative.Andtherewashappiness.AndwetriumphedovertheEmpirebydesigningDijkstra'salgorithm,andveryefficientlyfindingsinglesourceshortestpaths,shortestpathweightfromstoeveryothervertex.Today,however,theDeathStarhasanewtrickupitssleeve,andw
5、ehavenegativeweights,potentially.Andwe'regoingtohavetosomehowdealwith,inparticular,negativeweightcycles.Andwesawthatwhenwehaveanegativeweightcycle,wecanjustkeepgoingaround,andaround,andaround,andgobackintimefarther,andfarther,andfarther.Andwecangettobearbitrarilyfarbackinthepast.An
6、dsothere'snoshortestpath,becausewhateverpathyoutakeyoucangetashorterone.Sowewanttoaddressthatissuetoday,andwe'regoingtocomeupwithanewalgorithmactuallysimplerthanDijkstra,butnotasfast,calledtheBellman-Fordalgorithm.And,it'sgoingtoallownegativeweights,andinsomesenseallownegativeweigh
7、tcycles,althoughmaybenotasmuchasyoumighthope.Wehavetoleaveroomforasequel,ofcourse.OK,sotheBellman-Fordalgorithm,inventedbytwoguys,asyoumightexpect,itcomputestheshortestpathweights.So,itmakesnoassumptionabouttheweights.Weightsarearbitrary,andit'sgoingtocomputetheshortestpathweights.
8、So,rememberthisnotation:de
