杭电最短路径（hangzhou electric shortest path）

《杭电最短路径（hangzhou electric shortest path）》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、杭电1874最短路径（HangzhouElectric1874shortestpath）HDU1874comparisonbasis,usedtopracticeavarietyofjustlearnedalgorithmisbetter,youcanavoidmanytraps,typicalofthemostshort-circuittemplateproblemsThefirstsolution:FloydalgorithmAlgorithmimplementation:Useanadjacencymatrixt

2、ostoretheedgeweights.Thenumberofaccessesbetween22mustbeafinitenumber,andifnotaccessible,itisinfinite(replacedby2^29).Notethatthedistancebetweenyourselfandyourselfis0.ForapairofverticesuandV,seeifthereisabreakpointwthatmakesWfromutoVshorterthantheknownpath(includ

3、ingthedirectentryfromutoVintherawinput).Forallvertexrelaxationoperations,theresultistheshortestdistancebetweentwopoints,anditcanalsobeusedtodeterminewhetherthetwopointsareconnected.Algorithmshortcomings:TheordinaryFloydalgorithmhasatimecomplexityofO(n^3)andiseas

4、ytoTLEformoredata.Buttosolvetheproblem,HDU1874isquiteenough.#include"stdio.h""#defineMax0xfffffffInt,N,m,map[201][201];Intmin(int,x,int,y){Returnx>y?Y:x?;}Void(getmap)//initialize{Int,a,B,I,J,l;For(i=0;i

5、++){Scanf("%d%d%d","&a","&b","&l");Map[a][b]=map[b][a]=min(map[a][b],l);}}VoidFloyd(int,s,int,e){Int,I,J,k;For(k=0;k

6、数，e；而（scanf（“%d%d”，与N和M）！=EOF）{getmap()；scanf（“%d%d”，&，&E）；弗洛依德（S，E）；}返回0；}---------------------------------------------------------------------------------------------第二种解法：Dijkstra算法这个算法比较经典，一般的最短路径都可以用这个来解决，耗时也比较少，不过不能处理负权路径按路径长度递增次序产生最短路径算法：把V分成两组：（1）：已求出最短路

7、径的顶点的集合（2）：尚未确定最短路径的顶点集合V-S=T将T中顶点按最短路径递增的次序加入到的中，保证：（1）从源点V0的中各顶点的最短路径长度都不大于到从V0到T中任何顶点的最短路径长度（2）每个顶点对应一个距离值的中顶点：从V0到此顶点的最短路径长度T中顶点：从V0的中顶点作中间到此顶点的只包括顶点的最短路径长度依据：可以证明V0到T中顶点VK的最短路径，或是从V0到VK的直接路径的权值；OrthesumofthepathweightsfromV0throughverticesinStoVk(proofofcon

8、tradiction)SeektheshortestpathstepThealgorithmstepsareasfollows:1.early,sothattheseasonS={V0},T={,therestofthevertex},TcorrespondingtothevertexdistancevalueIfthereis<