资源描述：
《transcript17》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、VideoLectures-Lecture17Topicscovered:ShortestPathsI:Properties,Dijkstra'sAlgorithm,Breadth-firstSearchInstructors:Prof.ErikDemaineProf.CharlesLeisersonTranscript-Lecture17We'regoingtotalkaboutshortestpaths,andwe'regoingtotalkaboutshortestpathsforthre
2、electures.So,thisisatrilogy.TodaywillbeShortestPathsOne.I'vebeenwatchingfartoomanyversionsofStarWarsthisweekend.Isawthemusicalyesterday,matinee.ThatwasanMITmusical.Thatwasfun,ofallthreemoviesinaboutfourhours.ThatwasabitlongandthenIsawtheone-manshowon
3、Friday.One-manStarWars:theoriginalthreemoviesinonehour.Thatwastheoppositeoftoolong.Bothwerefun.SoIgetmytrilogyfix.Allepisodes,firstwe'regoingtostartwithTheNewHope,andwe'regoingtotalkabouttheshortestpathsproblemandsolveoneparticularproblemofit,averyin
4、terestingversion.Andthenwe'regoingtolookatincreasinglymoregeneralversionsaswegoon.Shortestpathsaresortofanapplicationofdynamicprogramming,whichwesawlastweek,andgreedyalgorithms,whichwealsosawlastweek.So,weregoingtobuildthatandgetsomeprettyinteresting
5、algorithmsforanimportantproblem,whichishowtogetfromAlderonto,Idon'tknow,Cambridgeasquicklyaspossible,OK,whenyouliveinagraph.So,there'sgeometricshortestpathswhichisalittlebitharder.Here,we'rejustgoingtolookatshortestpathsingraphs.Now,hopefullyyouallkn
6、owwhatapathinagraphis.But,so,veryquickreviewinparticularbecausewe'regoingtobelookingatweightedgraphs.So,theusualsetup:supposewehavedirectedgraph,G,havesomevertices,someedges.Wehaveedgeweights,makeitalittlemoreinteresting.So,thisisjustarealnumberoneac
7、hedge.So,edgeweightsareusuallygivenbyfunction,w.Foreveryedge,yougetarealnumber.Andthen,ifwelookatthepathsinthegraph,sowe'regoingtousesomesimplenotationforpathscalledapath,p,startsatsomevertex,anditgoestosomeothervertex,andsoon.Saythelastvertexisv_k,a
8、ndeachoftheseshouldbeadirectededgeinthedigraph.So,thisisadirectedpath.Ithastorespectedgesinhere.And,we'llsaythattheweightofsuchapathisjustthesumoftheweightsoftheedgesalongthepath.And,we'llcallthatw(p).Thisissum,iequalsonetokminusoneofw(v_i,v_(i+1))pl
