欢迎来到人人文库网! | 帮助中心 人人文库renrendoc.com美如初恋!
人人文库网
首页 人人文库网 > 资源分类 > DOC文档下载

Dijkstra算法.doc

  • 资源大小:69.00KB        全文页数:12页
  • 资源格式: DOC        下载权限:游客/注册会员/VIP会员    下载费用:3
游客快捷下载 游客一键下载
会员登录下载
下载资源需要3

邮箱/手机号:
您支付成功后,系统会自动为您创建此邮箱/手机号的账号,密码跟您输入的邮箱/手机号一致,以方便您下次登录下载和查看订单。注:支付完成后需要自己下载文件,并不会自动发送文件哦!

支付方式: 微信支付    支付宝   
验证码:   换一换

友情提示
2、本站资源不支持迅雷下载,请使用浏览器直接下载(不支持QQ浏览器)
3、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰   

Dijkstra算法.doc

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

注意事项

本文(Dijkstra算法.doc)为本站会员(baixue100)主动上传,人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知人人文库网(发送邮件至[email protected]或直接QQ联系客服),我们立即给予删除!

温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。

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

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

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

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