算法设计与分析短路径ich24est paths ilet11.pptx

DesignandAnalysisofAlgorithms

ShortestPathsI(Ch24)

2DesignandAnalysisofAlgorithmsShortestPathsITopics:ShortestpathsDijkstra’algorithm

3PathsingraphsConsideradigraphG=(V,E),withedge-weightfunctionw:E?R.Theweightofpathp=v1?v2--…?vkisdefinedtobew(p)=∑i=1..k-1w(vi,vi+1)Example:

4ShortestpathsAshortestpathfromutovisapathofminimumweightfromutov.Theshortest-pathweightformutovisdefinedas

5OptimalstructureTheorem.Asubgraphofshortestpathisashortestpath.Proof.Cutandpaste:v6

6TriangleinequalityTheorem.Forallu,v,x∈V,wehaveδ(u,v)≤δ(u,x)+δ(x,v)Proof.

7Well-definednessofshortestpathsIfagraphGcontainsanegative-weightcycle,thensomeshortestpathsmaynotexist.

8Single-sourceshortestpathsProblem.Fromagivensourcevertexs∈V,findtheshortest-pathweightδ(s,v)forallv∈V.Ifalledgeweightw(u,v)arenonnegative,allshortest-pathweightsmustexist.IDEA:Greedy1.MaintainasetSofverticeswhoseshortest-pathdistancesfromsareknown2.AteachstepaddtoSthevertexv∈V-Swhosedistanceestimatefromsisminimal.3.Updatethedistanceestimatesofverticesadjacenttov.

9Dijkstra’salgorithm

10ExampleofDijkstra’salgorithmGraphwithnonnegativeedgeweights:

11ExampleofDijkstra’salgorithmInitialize:

12ExampleofDijkstra’salgorithm

13ExampleofDijkstra’salgorithmRelaxalledgesleavingA:

14ExampleofDijkstra’salgorithm

15ExampleofDijkstra’salgorithmRelaxalledgesleavingC:

16ExampleofDijkstra’salgorithm

17ExampleofDijkstra’salgorithmRelaxalledgesleavingE:

18ExampleofDijkstra’salgorithm

19ExampleofDijkstra’salgorithmRelaxalledgesleavingB:

20ExampleofDijkstra’salgorithm

21SimpleReviewKnapsackProblem0/1HuffmancodesShortestpathsDijkstra’salgorithm

22Dijkstra’salgorithm

23AnalysisofDijkstra’salgorithmHanshakingLemma?Θ(E)implicitDECREASE-KEY’sTime=Θ(V.TEXTRACT-MIN+E.TDECREASE-KEY)Note: