最优路径算法.doc_第1页
最优路径算法.doc_第2页
最优路径算法.doc_第3页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

解决方案一：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顶点的最短距离distj=mindistj,disti+matrixij。根据这种思路，假设存在G=，源顶点为V0，U=V0,disti记录V0到i的最短距离，pathi记录从V0到i路径上的i前面的一个顶点。1.从V-U中选择使disti值最小的顶点i，将i加入到U中；2.更新与i直接相邻顶点的dist值。(distj=mindistj,disti+matrixij)3.知道U=V，停止。测试数据：运行结果：解决方案2ArcGIS for Android 查找最短路径ArcGIS for Android（10.1.1）只支持在线的网络分析，执行路径分析可以通过RoutingTask类的solve方法来进行，通过给slove方法传递RoutingParameters类型的参数，可以最短路径的查找。而要成功执行路径分析，就必须发布网络分析服务，比较麻烦，下面的代码中使用的服务是arcgisonline.上已经发布的服务。以下代码程序的界面如下：界面包含两控件：TextView和MapView，在执行路径分析前单击MapView会增加路径分析的停靠点，长按MapView会根据停靠点（至少要两个停靠点）执行查找最短路径的操作，执行成功之后会在TextView中显示相关的路径信息，这时候单击查询的路径，会
人人文库> 全部分类> 生活休闲 > 科普知识

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论