文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > IT/计算机 > 计算机软件及应用 > 最短路径算法,基于真实道路网络下评价
侵权投诉

最短路径算法,基于真实道路网络下评价

毕业译文,其英语文献,请于百度搜索“Shortest path algorithms An evaluation using real road networks (1998)”

用堆栈顺序标记节点处理的算法明显低于其余的算法,因此,该算法也一般不考虑。

在进入正文之前,先引入一些关于最短路径问题的符号和定义。网络是由一个图G (N,A)组成的索引节点N,n N,生成树集为A,m A。每个弧表示一对有序节点,从节点i到节点j,以(i,j)的形式表示。每个弧(i,j)都具有一个关联的数值——dij,它代表遍历弧的距离或成本。在本文中,我们假定在一对节

点i和j之间的双向运动的线段表示的两个不同的有向弧(i,j)和(j,i)。给定一个有向网络G (N,A)与已知弧长dij,对于每个弧有 i,j A,最短路问题就是找

到最短的距离路径从源节点s到其他节点的N的节点集。这些从vs到所有节点的

最短路径,可以作为一个以源节点s为定向的树,这个定向树表示被称为作为一个最短路径树。

在本文的研究中对于所有的算法都是基于标记方法来评估的,但算法根据选择扫描标记的节点所使用的规则的不同,因而用于管理标记的节点的集合的数据结构也就不同了。读者认为1988年的加洛 、pallottino和 1993年的切尔卡斯基等人的文献能更全面地讨论问题。在本文的研究中评估的具体算法总结于表1.1。切尔卡斯基等人(1993)的算法和这些算法实现的详细信息在表1.1中所列的其他参考文献中都可以找到。这些算法可以分为以下五类:1)贝尔曼-福特-摩尔算法,2)迪杰斯特拉算法,3)渐进式算法,4)阈值算法,以及5)拓扑排序。同时再进一步迪杰斯特拉算法的实现进行分类,无论是简单结构,斗式结构,或堆结构。应该指出的是,在最坏情况下的计算复杂度的测试算法包括多项式(多项式m和n),拟多项式多项式(n,m和C)和指数(PAPE算法)。

在迪杰斯特拉算法中有一个节点的选择定则,这明显不同于其他算法,其确保“永久性标记”一次一个节点的最短路径树构造规则。一旦一个节点是永久性标记,其最优最短路径距离源节点是已知的。因此,假如只是要找到最短的路径从一个节点到其他节点(一对一最短路径问题),可以使迪杰斯特拉算法将目的节点记为是永久标记,那么所有其他的任何目标,通过算法找到最佳最短路径,以形成完整的最短路径树

上一页第3页

你可能喜欢

  • 英文文献翻译
  • 弗洛伊德算法
  • Floyd算法
  • Dijkstra算法
  • 消防规划
  • 应急物资调度
  • 蚁群算法

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email