《表2 不同尺度子图分割方法求解的最短路径距离》

  提示：宽带有限、当前游客访问压缩模式

本系列图表出处文件名：随高清版一同展现

《基于云计算的大规模交通路网的最短路径算法》

1. 获取 高清版本忘记账户？点击这里登录

1. 下载图表忘记账户？点击这里登录

表3显示了计算时间的差异，TT代表框架的总计算时间（单位:s），包括数据结构初始化、子图投射和最短路径执行时间；TS表示最短路径计算时间（单位:s）.结果显示，直接使用Dijkstra算法的平均计算时间约为386.6 s，最短路径计算时间约为4.2 s.相比而言，本文所提出的算法性能在计算时间和解的优劣取决于子图的大小.当D=20 km时，Hadoop框架的平均计算时间约为104 s，速度比直接使用Dijkstra算法快约4倍，而且不同实例差异较大，主要取决于图结构，尤其是图的稀疏程度；当子图大小为100 km时，可得到最佳效率，平均计算时间约为58.13 s，最短路径所需的计算时间小于总时间的1%.由此可知，数据结构管理和图形投射耗时较高.例如，实例1整个图大约要管理4 GB的数据，初始化数据结构和实现内存中的额外计算共需要381s，而执行最短路径计算只需要0.2 s.