麻省理工大学算法导论lecture19

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

1、IntroductiontoAlgorithms6.046J/18.401J/SMA5503Lecture19Prof.ErikDemaineShortestpathsSingle-sourceshortestpaths•Nonnegativeedgeweights≠Dijkstra’salgorithm:O(E+VlgV)•General≠Bellman-Ford:O(VE)•DAG≠OnepassofBellman-Ford:O(V+E)All-pairsshortestpaths•Nonnegativeedgeweights≠Dijkstra’salgori

2、thm

3、V

4、times:O(VE+V2lgV)•General≠Threealgorithmstoday.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay32L19.2All-pairsshortestpathsInput:DigraphG=(V,E),where

5、V

6、=n,withedge-weightfunctionw:E→R.Output:n×nmatrixofshortest-pathlengthsδ(i,j)foralli,j∈V.IDEA#1:•RunBellman-Fordoncefromeac

7、hvertex.•Time=O(V2E).•Densegraph⇒O(V4)time.Goodfirsttry!©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay32L19.3DynamicprogrammingConsiderthen×nadjacencymatrixA=(a)ijofthedigraph,anddefined(m)=weightofashortestpathfromijitojthatusesatmostmedges.Claim:Wehave(0)0ifi=j,d=ij∞ifi≠j;andf

8、orm=1,2,…,n–1,d(m)=min{d(m–1)+a}.ijkikkj©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay32L19.4Proofofclaimk’sd(m)=min{d(m–1)+a}ijkikkjsegde1–m≤segde1–mi≤jii≤jm–1MedgeRelaxation!sfork←1tondoifd>d+aijikkjthendij←dik+akj≤m–1edgesNote:Nonegative-weightcyclesimpliesδ(i,j)=d(n–1)=d(n)=

9、d(n+1)=Lijijij©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay32L19.5MatrixmultiplicationComputeC=A·B,whereC,A,andBaren×nmatrices:ncij=∑aikbkj.k=1Time=Θ(n3)usingthestandardalgorithm.Whatifwemap“+”→“min”and“·”→“+”?c=min{a+b}.ijkikkjThus,D(m)=D(m–1)“×”A.0∞∞∞∞0∞∞0(0)Identitymatri

10、x=I=∞∞0∞=D=(dij).∞∞∞0©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay32L19.6Matrixmultiplication(continued)The(min,+)multiplicationisassociative,andwiththerealnumbers,itformsanalgebraicstructurecalledaclosedsemiring.Consequently,wecancomputeD(1)=D(0)·A=A1D(2)=D(1)·A=A2MMD(n–

11、1)=D(n–2)·A=An–1,yieldingD(n–1)=(δ(i,j)).Time=Θ(n·n3)=Θ(n4).Nobetterthann×B-F.©2001byCharlesE.LeisersonIntroductiontoAlgorithmsDay32L19.7ImprovedmatrixmultiplicationalgorithmRepeatedsquaring:A2k=Ak×Ak.242lg(n–1)ComputeA,A,…,A.O(lgn)squaringsNote:An–1=An=An+1=L.Time=Θ(n3lgn).Todetect

12、negat