...
  • 主题
高级搜索  >
历史搜索 清空历史
首页> 外文期刊>Journal of network and computer applications >FB-APSP: A new efficient algorithm for computing all-pairs shortest-paths
【24h】

FB-APSP: A new efficient algorithm for computing all-pairs shortest-paths

机译：FB-APSP：一种用于计算所有对最短路径的高效新算法

获取原文
获取原文并翻译 | 示例
           
页面导航
  • 摘要
  • 著录项
  • 相似文献
  • 相关主题

摘要

We describe a new forward-backward method for an all-pairs shortest-paths (APSP) algorithm. While most APSP algorithms only scan edges forward, the algorithm proposed here also scans all edges backward because it assumes that edges in the outgoing and incoming adjacency lists of the vertices appear with the same importance. The running time of the algorithm on a directed graph with n vertices, and m edges and positive real valued edge weights in a deterministic way is O (n delta(2)[2(log delta(n-1))-1]), and the space complexity is O (n delta[2(log delta(n-1)-1)]), where delta = m is the density of the graph. Simulations on graphs with up to 10000 vertices with real, positive weights show that our FB-APSP algorithm, using additional working space less than 75% of space used by Speed Up Floyd-Warshall algorithm, is faster on large sparse graphs, particularly planar graphs.
机译：我们描述了一种用于全对最短路径（APSP）算法的新的前进-后退方法。尽管大多数APSP算法仅向前扫描边缘，但此处提出的算法也向后扫描所有边缘，因为它假定顶点的输出邻接列表中的边缘具有相同的重要性。该算法在具有n个顶点，m个边和确定的正实值边权重的有向图上的运行时间为O（n delta（2）[2（log delta（n-1））-1]） ，空间复杂度为O（n delta [2（log delta（n-1）-1）]），其中delta = m / n是图的密度。对具有多达10000个顶点的，具有真实正权重的图进行的仿真表明，我们的FB-APSP算法使用的额外工作空间小于Speed Up Floyd-Warshall算法使用的空间的75％，在大型稀疏图（尤其是平面图）上速度更快。

著录项

相似文献

  • 外文文献
  • 中文文献
  • 专利
获取原文

客服邮箱：kefu@zhangqiaokeyan.com

京公网安备：11010802029741号 ICP备案号：京ICP备15016152号-6 六维联合信息科技 (北京) 有限公司©版权所有

  • 客服微信

  • 服务号