会员注册 | 登录 | 微信快捷登录 支付宝快捷登录 QQ登录 微博登录 | 帮助中心 人人文库renrendoc.com美如初恋!
站内搜索 百度文库

热门搜索: 直缝焊接机 矿井提升机 循环球式转向器图纸 机器人手爪发展史 管道机器人dwg 动平衡试验台设计

   首页 人人文库网 > 资源分类 > DOC文档下载

Dijkstra算法.doc

  • 资源星级:
  • 资源大小:69.00KB   全文页数:12页
  • 资源格式: DOC        下载权限:注册会员/VIP会员
您还没有登陆,请先登录。登陆后即可下载此文档。
  合作网站登录: 微信快捷登录 支付宝快捷登录   QQ登录   微博登录
友情提示
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表为空,或找到目标点。编辑本段算法实现includedefineMaxNum765432100usingnamespacestdifstreamfinDijkstra.inofstreamfoutDijkstra.outintMap501501boolis_arrived501intDist501,From501,Stack501intp,q,k,Path,Source,Vertex,Temp,SetCardintFindMin{intp,Temp0,MinmMaxNumforp1pSourceVertexforp1pMappqifMappq0MappqMaxNum}forp1pDistTempMapTemppis_arrivedp{DistpDistTempMapTemppFrompTemp}}elsebreak}whileSetCardVertexforp1p1Source2Target3Distance25Path23Source2Target4Distance50Path214Source2Target5Distance50Path235Source2Target6Distance60Path2356Source2Target7DistanceInfinityPathNoWay示例程序及相关子程序voidDijkstraintn,intDistance,intiPath{intMinDis,uinti,j//从邻接矩阵复制第n个顶点可以走出的路线,就是复制第n行到Distancefori0i0{ifmMinAdjNoden1{Tn.Nodes.AddTmnmVisitedn}else{nMinNode0ifn0TMin2.Nodes.AddTMin1Visitedn}listBox1.Items.AddVn}treeView1.Nodes.AddT0}voidTopoSort{inti,nlistBox1.Items.ClearStackSnewStackfori0i0iifInDegreei0{S.PushiVisited}whileS.Count0{nintS.PoplistBox1.Items.AddVnClearLinknforiVerNum1i0iifVisited0InDegreei0{S.PushiVisited}}}voidAOETraveintn,TreeNodeTR,intw{inti,w0ifOutDegreen0returnfori0i0returnireturn1}intLineIsZerointn{intifori0i0{ifVisitedm0{listBox1.Items.AddVmRm1}VisitedmDTravem}fori0iVerNumi

注意事项

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

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

copyright@ 2015-2017 人人文库网网站版权所有
苏ICP备12009002号-5