算法分析与设计2003秋.课件.第08讲

《算法分析与设计2003秋.课件.第08讲》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、Lecture8.shortest-paths•Background–Tofindashortestroutefromonecitytoanother–Tofindaleasttimeroutefromoneplacetotheothers–Anymore?清华大学宋斌恒1•Descriptionoftheproblem•WeightedDirectedGraph•Weightfunction:w:EÆR•Pathp=012k•Weightofapath:kw(p)=∑w(vi−1,vi)i=1•S

2、hortestpathweightfromutovby:pmin{w(p)}:u→vifthereisapathfromutovδ(u,v)=∞清华大学宋斌恒otherwise21Problemanditsvariants•Single-Sourceshortest-path•Single-Destinationshortest-path•Single-pairshortest-path•All-pairsshortest-paths清华大学宋斌恒3Optimalsubstructureofashortestp

3、ath•Shortest-pathsalgorithmstypicallyrelyonthepropertythatashortestpathbetweentwoverticescontainsothershortestpathswithinit.•ConditionsforapplyingtheDynamicprogrammingandgreedymethod:•Optimalsubstructure.清华大学宋斌恒42Lemma24.1.•Subpathsofshortestpathsareshortestpaths

4、•Proof.Usingmethodofcutandpatse清华大学宋斌恒5Negativeweightedges•Mostoftheinstanceoftheproblemsarealloftheedgesarenonnegativeweight•Someoftheinstanceoftheproblemshavenegativeweightedges•Negativecycles:thenegativeinfinitivelength清华大学宋斌恒633－10511－∞－∞－∞清华大学宋斌恒7－∞－∞－∞清华大学宋

5、斌恒84Cycles•Canashortestpathcontainscycles:–Case1.PositiveCycles:neveroccurs–Case2.NegativeCycles:-∞–Case3.zeroCycles:removable清华大学宋斌恒9Representingshortestpaths•Usingpredecessorlabelcangettheresult.•LetG=(V,E)beagraph•π:VÆV∪{null}•Shortest-pathstreerootedatsisadir

6、ectedsubgraphG’=(V’,E’)ofG.–V’isthesetofverticesreachablefromsinG–G’formsarootedtreewithrootsand–Forallv∈V’,theuniquesimplepathfromstovinG’isashortestpathfromstovinG清华大学宋斌恒105390511清华大学宋斌恒11390511清华大学宋斌恒126390511清华大学宋斌恒13Relaxation•Weusingthetechniqueofrelaxation

7、:•Letd[v]beashortest-pathofestimate,itmustbegreatthanorequaltoitsrealdistanceofvfroms,thesource.•Initialize-Single-Source(G,s)1.Foreachvertexv∈V[G]1.d[v]=∞2.π[v]=null2.d[s]=0清华大学宋斌恒14759565756清华大学宋斌恒15Somecommentsonrelaxation•松弛什么？•Relaxtheconstrainoftriangleineq

8、uality清华大学宋斌恒168Relax•Relax(u,v,w)1.Ifd[v]>d[u]+w(u,v)1.d[v]Åd[u]+w(u,v)2.π[v]Åu清华大学宋斌恒17Propertiesandrelaxation1.Triangleinequality:forany(u,v)∈Ewehaveδ(s,v)≤