树是“永久的标记“一次一个节点构造。一旦一个节点被永久性标记,那么其最佳的最短路径从源节点是已知的。因此,如果从一个节点到其他节点的最短路径查找是必要的(一对一的最短路径问题),然而Dijkstra算法可以尽快的是节点的被永久的标记上。在所有其他的算法终止时,任何目的地只有满最短路径树才能保证最佳的最短路径的距离。
3.计算研究
实验设计包括网络数据和计算测试本身的制备。在美国中西部和东南部的十个州的道路网络,和道路网络构成的NHPN,覆盖了整个美国大陆,被用于测试最短路径算法。这十个被选为测试州,为测试提供了一个良好的方位的农村,郊区,城市结构。
在我们的研究中,创建和使用了两种道路网络数据集。包括两套不同网络的大小。数据集的1由十个低细节的道路网络组成,在我们的研究中为每一个州。设置使用的道路,最高三层生成,即州际高速公路,主干道和主要干道,来自美国地质调查局的数字线划图。图1显示了密苏里道路网络数据集1。数据集包括十个国家两个高细节的道路网络,美国NHPN(简称US)。
图1密苏里低细节的道路网络数据集1
十个高细节状态网络加四分之一确定为农村未成年人动脉网络数据生成1路。图2说明了密苏里的道路网络数据集2。
5
图2密苏里高细节的道路网络数据集2
在地理信息系统的双向链路维护中,道路网络存储为一组节点。在ASCII文件的地理信息系统中下载节点,链路和链路长度。在下载网络文件之前,检查确保道路网络是完全连接的。两个有向弧创建了数据集的每个双向链路,因此,弧的数量总是等于链接的数量的两倍。这21个测试网络的特点在表II中给出。我们发现弧节点的比率在两组数据中无显著差异。地理中网络的弧长是十进制的。因为最短路径的代码需要整数距离输入,所以电弧长度乘以一个比例因子,以及由此产生的电弧长度被截断为整数。这种类型的缩放和截断影响了电弧的长度尺寸,可根据算法性能来判断。算法灵敏度的缩放因子的研究在本节的后一部分描述。
该程序用版本2.5.6的GNU GCC编译器使用O4优化选项编译。我们的实验是在一个独立的太阳sparc-20工作站上进行的,与一个125 MHz的hypersparc处理器和64 MB的Solaris 2.4环境下运行的RAM模型21。
报告的运行时表示计算最短路径树的CPU时间,不包括数据输入或输出的解决方案。对于每一个网络,以一个100节点随机选择样本时,指定为网络的示例源节点。对于一个给定组合的道路网络,算法,和缩放因子,所产生的100个最短路径树示由一个时间估计计算的。为了确保准确性,时间估计对应于一个单一源节点的平均时间,从数据的网络源节点产生1000个相同的数据集1。数据集2,产生10的平均时间(而不是1000)相同的树代表一个源节点的估计。对100个源节点的估计进行编译,计算平均与最大的个人时间的平均比率。
我们在第一组的计算结果中总结了各个算法的性能所对应的缩放因子为1000。之后,我们通过改变比例因子来对某些算法的电弧长度进行影响。表III显示的是算法的相对速度对数据集的1和2,与一个比例因子1000。在每个表中,
6
网络中越来越多的节点顺序和算法是通过增加整体的相对速度比来列序的(以粗体显示的列)。每个表中的最后一行是表现最好的算法,对于一个给定的网络使每个最短路径树都为平均CPU时间。行所对应的算法得到的平均CPU时间用每棵树来表现最好的算法对于网络的时间比的算法。例如,在表三,Pape是表现最好的算法,内布拉斯加州(NE)和平均CPU时间以每0.46毫秒来实现。表现最差的算法在内布拉斯加州网络DIKF每棵树都具有平均运行时间,比纸更大7.59倍。因此,对于DIKF的CPU时间,可以计算为7.59倍,0.46,或3.49毫秒。列标题下的“整体表现”显示的CPU时间persource节点,平均在所有网络的算法和相应的值的速度是最快的算法。
增量图算法(佩普和twoiq)在所有算法的两个数据集中占主导地位。最近得出的算法的两个数据集的阈值(阈值)平均每棵树的时间大约是40%,大于增量图算法。
Dijkstra算法的实现(dikba,DIKB,dikbd,dikbm)所表现出的数据集1的运行时间比从2.34增加到2.99,相对于PAP的运行时间。对大网络数据集2,运行时间范围大概稳定在1.53至1.67。
Dijkstra算法的堆实现(DIKF,dikh,DIKR)是将两个数据集聚集在一起。对数据集1,他们表现不佳的相对运行时间比例从5.12到8.24。在数据集2中,分别提高了dikh和DIKR 的相对性能比例为2.15和2.70。DIKF滞后于其他堆实现的相对比例。他们分别是数据集的1中的8.24和数据集的2中的4.31。
相比,表现最好的算法,Dijkstra算法的单纯实现(dikq)大约比数据集1慢五倍也比数据集2慢24倍。拓扑排序算法(GOR和gor1)在数据集1的比率为2.49和8.58。在数据集2,gor1保持相对缓慢,比例超过10,而关闭的性能差距的比例为1.62。Bellman–Ford–Moore算法的实现(BFP和BF)在2到3倍的时间上比数据集1快,然后表现得非常差的数据集2与约14和31的相对时间比率。
最后,表III提供了一个衡量算法的可预测性。对算法和网络的每个组合,根据个人的时间进行了计算最短路径树生成100个源节点和最大平均的平均时间比的计算。最后,给出了每一组网络中的最大平均的平均比率。高的平均比率意味着算法采取了将每个节点的平均时间与较长时间的一些源节点作比较。Bellman–Ford–Moore实现了数据集的最高平均比率。在Dijkstra算法的单纯实现中数据集1的效率有点低,而数据集2的效率较高。大多数其他算法对数据集都有相对较低的比例,这表明不论是不是源节点,他们都保持一致的速度性能。
7
表2网络的特点
网络名称 (缩写) 数据集1:9个状态网络与3个层次的道路
523 1646 3.14 0.874764 内布拉斯加州
(NE1)
842 2506 2.98 0.650305 阿拉巴马州(AL1)
951 2932 3.08 0.972436 明尼苏达州
(MN1)
1003 2684 2.68 0.573768 爱荷华州(IA1)
1156 3240 2.80 0.498810 密西西比州(MS1)
2155 6370 2.96 0.923088 弗罗里达州(FL1)
2391 7208 3.06 0.494730 密苏里州(MO1)
2437 6876 2.82 1.021526 路易斯安娜州
(LA1)
2878 8428 2.92 0.478579 美国佐治亚州
(GA1)
数据集2:9个状态网络与4个层次的道路和美国国家高速公路规划网
35793 98880 2.76 0.360678 路易斯安娜州
(LA2)
120582 3.02 0.232062 密西西比州(MS2) 39986
50109 133134 2.66 0.416212 弗罗里达州(FL2)
63407 208134 3.28 0.269823 爱荷华州(IA2)
65491 209340 3.20 0.410925 明尼苏达州
(MN2)
66082 185986 2.82 0.298232 亚拉巴马(AL2)
67899 204144 3.00 0.212470 密苏里州(MO2)
75417 205998 2.74 1.500361 美国nhpn (US2)
92792 264392 2.84 0.174245 美国佐治亚州
(GA2) *在一个地理坐标系统中电弧的长度是十进制的。
0.215551 0.128870 0.175173 0.119900 0.095443 0.075247 0.090977 0.060662 0.068333
节点数目 弧的数目 弧/节点的比例 最大 弧长* 平均数 StdDev函数 0.142461 0.114031 0.132083 0.113719 0.100703 0.076590 0.064761 0.067557 0.005668
0.013874 0.015412 0.011207 0.015733 0.017202 0.011383 0.015542 0.066084 0.010511
0.015297 0.014000 0.015264 0.009220 0.014107 0.012410 0.013266 0.094758 0.000107
8
表3比例因子为1000的数据的相对性能概要集
算法 PAPE TWO-Q THRESH BFP DIKBA DIKB GOR DIKBM DIKBD BF DIKQ DIKH DIKR DIKF GOR1
最小的CPU时间
NE1 1.00 1.08 1.87 1.43 4.33 4.33 2.47 4.63 3.75 1.74 3.24 4.61 6.37 7.59 6.90 0.46
AL1 1.00 1.08 1.58 1.57 2.86 2.87 2.47 3.20 3.48 2.09 4.39 5.37 6.08 8.25 7.70 0.73
网络的相对性能 MN1 1.00 1.08 1.52 1.59 2.91 2.92 2.49 3.14 3.29 2.21 4.07 4.71 5.82 7.82 7.26 0.90
MS1 1.00 1.09 1.49 2.36 2.34 2.35 2.59 2.66 2.95 3.10 4.17 4.87 5.20 7.57 7.59 1.09
SC1 1.00 1.08 1.44 1.95 2.15 2.16 2.50 2.42 2.90 2.65 5.12 5.26 5.20 8.42 8.51 1.63
FL1 1.00 1.07 1.51 1.99 2.31 2.33 2.42 2.53 2.96 3.34 3.93 4.68 5.24 7.73 8.83 2.08
GA1 1.00 1.06 1.33 2.51 1.95 1.97 2.47 2.31 2.67 4.05 5.88 5.31 4.78 8.23 8.86 2.87
整体性能 总时间 15.12 16.22 22.26 31.96 35.41 35.61 37.61 39.98 45.25 48.35 75.09 77.47 80.69 124.63 129.70 15.12
比率 1.00 1.07 1.47 2.11 2.34 2.36 2.49 2.64 2.99 3.20 4.97 5.12 5.34 8.24 8.58
这些值代表一个算法/网络组合的CPU时间比效率最好的算法时间还要短。给定的CPU时间是以毫秒为单位的。
明显的列里面:算法被命令通过增加整体的相对速度来提高算法的运行速度。
9