《表1 0 对Web-NotreDame使用不同策略和不同|L|个数求解的平均相对误差进行比较》

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

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

《大规模图数据边受限制的最短距离查询算法》

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

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

f代表向前路标节点的个数，e代表向后路标节点的个数，g代表向前核心节点的个数，h代表向后核心节点的个数。Select＿L（G，k，r）的运行时间复杂度是O（n）。Forward＿Cluster（）的运行时间是T（n）=dgn所以O（n）。Backward＿Cluster（）的运行时间是T（n）=ehn，时间复杂度为O（n）。所以算法总的时间复杂度是O（n）。因为使用斐波那契堆[38]来实现最小先队列的迪杰斯特拉算法的时间复杂度是O（n lg n+m），所以随机策略和度策略的时间复杂度是O（n lg n+m）。中心策略的时间复杂度是O（n2lg n+mn），改进的中心策略的时间复杂度是O（n lg n+m）。如表1所示为各种策略时间复杂度的比较，通过分析比较发现本文中的算法时间复杂度降低了。