Dijkstra算法.docDijkstra算法.doc

收藏 分享

资源预览需要最新版本的Flash Player支持。
您尚未安装或版本过低,建议您

DIJKSTRA算法DIJKSTRA算法是典型最短路算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。DIJKSTRA算法能得出最短路径的最优解,但由于它遍历计算的节点很多,所以效率低。DIJKSTRA算法是很有代表性的最短路算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。DIJKSTRA一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN,CLOSE表方式,DREW为了和下面要介绍的A算法和D算法表述一致,这里均采用OPEN,CLOSE表的方式。其采用的是贪心法的算法策略大概过程创建两个表,OPEN,CLOSE。OPEN表保存所有已生成而未考察的节点,CLOSED表中记录已访问过的节点。1.访问路网中距离起始点最近且没有被检查过的点,把这个点放入OPEN组中等待检查。2.从OPEN表中找出距起始点最近的点,找出这个点的所有子节点,把这个点放到CLOSE表中。3.遍历考察这个点的子节点。求出这些子节点距起始点的距离值,放子节点到OPEN表中。4.重复第2和第3步,直到OPEN表为空,或找到目标点。编辑本段算法实现INCLUDEFSTREAMDEFINEMAXNUM765432100USINGNAMESPACESTD;IFSTREAMFINDIJKSTRAIN;OFSTREAMFOUTDIJKSTRAOUT;INTMAP501501;BOOLIS_ARRIVED501;INTDIST501,FROM501,STACK501;INTP,Q,K,PATH,SOURCE,VERTEX,TEMP,SETCARD;INTFINDMIN{INTP,TEMP0,MINMMAXNUM;FORP1;PVERTEX;PIFDISTPMINMIS_ARRIVEDP{MINMDISTP;TEMPP;}RETURNTEMP;}INTMAIN{MEMSETIS_ARRIVED,0,SIZEOFIS_ARRIVED;FINSOURCEVERTEX;FORP1;PVERTEX;PFORQ1;QVERTEX;Q{FINMAPPQ;IFMAPPQ0MAPPQMAXNUM;}FORP1;PVERTEX;P{DISTPMAPSOURCEP;IFDISTPMAXNUMFROMPSOURCE;ELSEFROMPP;}IS_ARRIVEDSOURCETRUE;SETCARD1;DO{TEMPFINDMIN;IFTEMP0{SETCARDSETCARD1;IS_ARRIVEDTEMPTRUE;FORP1;PVERTEX;PIFDISTPDISTTEMPMAPTEMPPIS_ARRIVEDP{DISTPDISTTEMPMAPTEMPP;FROMPTEMP;}}ELSEBREAK;}WHILESETCARDVERTEX;FORP1;PVERTEX;PIFPSOURCE{FOUT\N;FOUTSOURCESOURCE\NTARGETP\N;IFDISTPMAXNUM{FOUTDISTANCEINFINITY\N;FOUTPATHNOWAY;}ELSE{FOUTDISTANCEDISTP\N;K1;PATHP;WHILEFROMPATHPATH{STACKKPATH;PATHFROMPATH;KK1;}FOUTPATHSOURCE;FORQK1;Q1;QFOUTSTACKQ;}FOUT\N\N\N;}FINCLOSE;FOUTCLOSE;RETURN0;}SAMPLEINPUT2700205030000000200025000070005025004025500030004000550000000025550010000070500010000000000000000000SAMPLEOUTPUTSOURCE2TARGET1DISTANCE20PATH21SOURCE2TARGET3DISTANCE25PATH23SOURCE2TARGET4DISTANCE50PATH214SOURCE2TARGET5DISTANCE50PATH235SOURCE2TARGET6DISTANCE60PATH2356SOURCE2TARGET7DISTANCEINFINITYPATHNOWAY示例程序及相关子程序VOIDDIJKSTRAINTN,INTDISTANCE,INTIPATH{INTMINDIS,U;INTI,J;//从邻接矩阵复制第N个顶点可以走出的路线,就是复制第N行到DISTANCEFORI0;IVERNUM;I{DISTANCEARCN,I;VISITED0;}//第N个顶点被访问,因为第N个顶点是开始点VISITEDN1;//找到该顶点能到其他顶点的路线、并且不是开始的顶点N、以前也没走过。//相当于寻找U点,这个点不是开始点NFORI0;IVERNUM;I{U0;MINDISNO;FORJ0;JVERNUM;JIFVISITEDJ0DISTANCEJMINDIS{MINDISDISTANCEJ;UJ;}//如范例P1871图G6,DISTANCENO,NO,10,NO,30,100,第一次找就是V2,所以U2//找完了,MINDIS等于不连接,则返回。这种情况类似V5。IFMINDISNORETURN;//确立第U个顶点将被使用,相当于ARCV,UARCU,W中的第U顶点。VISITEDU1;//寻找第U个顶点到其他所有顶点的最小路,实际就是找ARCU,J、J取值在0,VERNUM。//如果有ARCI,UARCU,JARCI,J,则ARCI,JARCI,UARCU,JARCI,J//实际中,因为DISTANCE是要的结果,对于起始点确定的情况下,就是//如果DISTANCEUARCU,JDISTANCEJ则//DISTANCEJDISTANCEUARCU,J;//而IPATH保存了U点的编号;//同理对新找出的路线,要设置VISITEDJ0,以后再找其他路,这个路可能别利用到。例如V3FORJ0;JVERNUM;JIFVISITEDJ0ARCU,JNOUJ{IFDISTANCEUARCU,JDISTANCEJ{DISTANCEJDISTANCEUARCU,J;VISITEDJ0;IPATHJU;}}}}//辅助函数VOIDPRIM{INTI,M,N0;FORI0;IVERNUM;I{VISITED0;TNEWTREENODE;TTEXTV;}VISITEDN;LISTBOX1ITEMSADDVN;WHILEVISIT0{IFMMINADJNODEN1{TNNODESADDTM;NM;VISITEDN;}ELSE{NMINNODE0;IFN0TMIN2NODESADDTMIN1;VISITEDN;}LISTBOX1ITEMSADDVN;}TREEVIEW1NODESADDT0;}VOIDTOPOSORT{INTI,N;LISTBOX1ITEMSCLEAR;STACKSNEWSTACK;FORI0;IVERNUM;IVISITED0;FORIVERNUM1;I0;IIFINDEGREEI0{SPUSHI;VISITED;}WHILESCOUNT0{NINTSPOP;LISTBOX1ITEMSADDVN;CLEARLINKN;FORIVERNUM1;I0;IIFVISITED0INDEGREEI0{SPUSHI;VISITED;}}}VOIDAOETRAVEINTN,TREENODETR,INTW{INTI,W0;IFOUTDEGREEN0RETURN;FORI0;IVERNUM;IIFW0ARCN,I0{LISTBOX1ITEMSADDV\TWW0TOSTRING\TITOSTRING\TNTOSTRING;TREENODET1NEWTREENODE;T1TEXTVWWW0TOSTRING;TRNODESADDT1;AOETRAVEI,T1,WW0;}}VOIDAOE{INTI,W0,M1;TREENODET1NEWTREENODE;FORI0;IVERNUM;I{VISITED0;}T1TEXTV0;LISTBOX1ITEMSADD双亲表示法显示这个生成树;LISTBOX1ITEMSADDV\TW\TID\TPID;FORI0;IVERNUM;I{IFWARC0,I0{LISTBOX1ITEMSADDV\TWTOSTRING\TITOSTRING\T0;TREENODET2NEWTREENODE;T2TEXTVWWTOSTRING;AOETRAVEI,T2,W;T1NODESADDT2;LISTBOX1ITEMSADD\T\T树MTOSTRING;M;}}TREEVIEW1NODESCLEAR;TREEVIEW1NODESADDT1;}INTISZERO{INTI;FORI0;IVERNUM;IIFLINEISZEROI0RETURNI;RETURN1;}INTLINEISZEROINTN{INTI;FORI0;IVERNUM;IIFARCN,I0RETURNI;RETURN1;}VOIDDEPTHTRAVERSE{INTI,M;FORI0;IVERNUM;I{VISITED0;TNEWTREENODE;TTEXTV;R0;}WHILEMISZERO0{IFVISITEDM0{LISTBOX1ITEMSADDVM;RM1;}VISITEDM;DTRAVEM;}FORI0;IVERNUM;I
编号:201312142359028279    类型:共享资源    大小:69.00KB    格式:DOC    上传时间:2013-12-14
  
3
关 键 词:
IS 电气 高压 110kv 220kv 550kv 800kv
  人人文库网所有资源均是用户自行上传分享,仅供网友学习交流,未经上传用户书面授权,请勿作他用。
关于本文
本文标题:Dijkstra算法.doc
链接地址:http://www.renrendoc.com/p-218279.html

当前资源信息

4.0
 
(2人评价)
浏览:14次
baixue100上传于2013-12-14

官方联系方式

客服手机:17625900360   
2:不支持迅雷下载,请使用浏览器下载   
3:不支持QQ浏览器下载,请用其他浏览器   
4:下载后的文档和图纸-无水印   
5:文档经过压缩,下载后原文更清晰   

精品推荐

相关阅读

人人文库
关于我们 - 网站声明 - 网站地图 - 资源地图 - 友情链接 - 网站客服客服 - 联系我们

网站客服QQ:2846424093    人人文库上传用户QQ群:460291265   

[email protected] 2016-2018  renrendoc.com 网站版权所有   南天在线技术支持

经营许可证编号:苏ICP备12009002号-5