算法分析与设计2004春.课件.第08讲

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

1、Lecture8.shortest-paths¢Background¢Tofindashortestroutefromonecitytoanother¢Tofindaleasttimeroutefromoneplacetotheothers¢工作流中的最短完成时间？¢Anymore?清华大学宋斌恒1Descriptionoftheproblem¢WeightedDirectedGraph¢Weightfunction:w:EÆR¢Pathp=¢Weightofapath:kw(p)=∑w(vi−1,vi)i=1¢Shortestpathweightfromuto

2、vby:pmin{w(p)}:u→vifthereisapathfromutovδ(u,v)=∞otherwise清华大学宋斌恒21Problemanditsvariants¢Single-Sourceshortest-path¢Single-Destinationshortest-path¢Single-pairshortest-path¢All-pairsshortest-paths清华大学宋斌恒3Optimalsubstructureofashortestpath¢Shortest-pathsalgorithmstypicallyrelyonthepropertythatas

3、hortestpathbetweentwoverticescontainsothershortestpathswithinit.¢ConditionsforapplyingtheDynamicprogrammingandgreedymethod:¢Optimalsubstructure.清华大学宋斌恒42Lemma24.1.¢Subpathsofshortestpathsareshortestpaths¢Proof.Usingmethodofcutandpatse清华大学宋斌恒5Negativeweightedges¢Mostoftheinstanceoftheproblemsareallo

4、ftheedgesarenonnegativeweight¢Someoftheinstanceoftheproblemshavenegativeweightedges¢Negativecycles:thenegativeinfinitivelength清华大学宋斌恒633－10511－∞－∞－∞清华大学宋斌恒7－∞－∞－∞清华大学宋斌恒84Cycles¢Canashortestpathcontainscycles:¢Case1.PositiveCycles:neveroccurs¢Case2.NegativeCycles:-∞¢Case3.zeroCycles:removable清华大学宋斌

5、恒9Representingshortestpaths¢Usingpredecessorlabelcangettheresult.¢LetG=(V,E)beagraph¢π:VÆV∪{null}¢Shortest-pathstreerootedatsisadirectedsubgraphG’=(V’,E’)ofG.¢V’isthesetofverticesreachablefromsinG¢G’formsarootedtreewithrootsand¢Forallv∈V’,theuniquesimplepathfromstovinG’isashortestpathfromstovinG清华大

6、学宋斌恒105390511清华大学宋斌恒11390511清华大学宋斌恒126390511清华大学宋斌恒13Relaxation¢Weusingthetechniqueofrelaxation:¢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清华大学宋斌恒15Som

7、ecommentsonrelaxation¢松弛什么？¢Relaxtheconstrainoftriangleinequality清华大学宋斌恒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)∈Ew