分享
分销 收藏 举报 申诉 / 3

类型最优路径算法.doc

  • 上传人:pc****0
  • 文档编号:9440033
  • 上传时间:2025-03-26
  • 格式:DOC
  • 页数:3
  • 大小:148KB
  • 下载积分:10 金币
  • 配套讲稿:

    如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。

    特殊限制:

    部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。

    关 键  词:
    最优 路径 算法
    资源描述:
    解决方案一: Dijkstra算法(单源最短路径) 单源最短路径问题,即在图中求出给定顶点到其它任一顶点的最短路径。在弄清楚如何求算单源最短路径问题之前,必须弄清楚最短路径的最优子结构性质。 一.最短路径的最优子结构性质 该性质描述为:如果P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,k和s是这条路径上的一个中间顶点,那么P(k,s)必定是从k到s的最短路径。下面证明该性质的正确性。 假设P(i,j)={Vi....Vk..Vs...Vj}是从顶点i到j的最短路径,则有P(i,j)=P(i,k)+P(k,s)+P(s,j)。而P(k,s)不是从k到s的最短距离,那么必定存在另一条从k到s的最短路径P'(k,s),那么P'(i,j)=P(i,k)+P'(k,s)+P(s,j)<P(i,j)。则与P(i,j)是从i到j的最短路径相矛盾。因此该性质得证。 二.Dijkstra算法 由上述性质可知,如果存在一条从i到j的最短路径(Vi.....Vk,Vj),Vk是Vj前面的一顶点。那么(Vi...Vk)也必定是从i到k的最短路径。为了求出最短路径,Dijkstra就提出了以最短路径长度递增,逐次生成最短路径的算法。譬如对于源顶点V0,首先选择其直接相邻的顶点中长度最短的顶点Vi,那么当前已知可得从V0到达Vj顶点的最短距离dist[j]=min{dist[j],dist[i]+matrix[i][j]}。根据这种思路, 假设存在G=<V,E>,源顶点为V0,U={V0},dist[i]记录V0到i的最短距离,path[i]记录从V0到i路径上的i前面的一个顶点。 1.从V-U中选择使dist[i]值最小的顶点i,将i加入到U中; 2.更新与i直接相邻顶点的dist值。(dist[j]=min{dist[j],dist[i]+matrix[i][j]}) 3.知道U=V,停止。   测试数据:      运行结果:    解决方案2 ArcGIS for Android 查找最短路径 ArcGIS for Android(10.1.1)只支持在线的网络分析,执行路径分析可以通过RoutingTask类的solve方法来进行,通过给slove方法传递RoutingParameters类型的参数,可以最短路径的查找。而要成功执行路径分析,就必须发布网络分析服务,比较麻烦,下面的代码中使用的服务是arcgisonline.上已经发布的服务。以下代码程序的界面如下: 界面包含两控件:TextView和MapView,在执行路径分析前单击MapView会增加路径分析的停靠点,长按MapView会根据停靠点(至少要两个停靠点)执行查找最短路径的操作,执行成功之后会在TextView中显示相关的路径信息,这时候单击查询的路径,会选中路径片段,相关的信息也会在TextView上显示。单击TextView就会清空所有结果,恢复到原始状态。 结果:
    展开阅读全文

    开通VIP折扣优惠下载文档

    提示  咨信网声明:本文档由用户上传并分享,仅供学习交流、研究之用,未经授权,严禁复制、发行、汇编、翻译或网络传播等,侵权必究。

    咨信网小贴示:
    1、浏览或下载可查看了解,请点击【咨信网告知】。
    2、下载文件中如有侵权或不适当内容,将立即纠正。
    3、如果因为网速或其他原因下载失败请重新下载,重复下载[60天内]不扣币。
    4、开具发票登录电脑端申请,请点击【索取发票】。

    咨信网客服组:【微信客服】

    自信AI创作助手
    关于本文
    本文标题:最优路径算法.doc
    链接地址:https://www.zixin.com.cn/doc/9440033.html

    Copyright ©2010-2026   All Rights Reserved  宁波自信网络信息技术有限公司 版权所有   |  客服电话:0574-28810668    微信客服:咨信网客服    投诉电话:18658249818   

    违法和不良信息举报邮箱:help@zixin.com.cn    文档合作和网站合作邮箱:fuwu@zixin.com.cn    意见反馈和侵权处理邮箱:1219186828@qq.com   | 证照中心

    12321jubao.png12321网络举报中心 电话:010-12321  jubao.png中国互联网举报中心 电话:12377   gongan.png浙公网安备33021202000488号  icp.png浙ICP备2021020529号-1 浙B2-20240490   


    关注我们 :微信公众号  抖音  微博  LOFTER               

    自信网络  |  ZixinNetwork