首页> 外文会议>Experimental algorithms >Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study
【24h】

Batch Dynamic Single-Source Shortest-Path Algorithms: An Experimental Study

机译:批处理动态单源最短路径算法:一项实验研究

获取原文
获取原文并翻译 | 示例

摘要

A dynamic shortest-path algorithm is called a batch algorithm if it is able to handle graph changes that consist of multiple edge updates at a time. In this paper we focus on fully-dynamic batch algorithms for single-source shortest paths in directed graphs with positive edge weights. We give an extensive experimental study of the existing algorithms for the single-edge and the batch case, including a broad set of test instances. We further present tuned variants of the already existing SWSF-FP-algorithm being up to 15 times faster than SWSF-FP. A surprising outcome of the paper is the astonishing level of data dependency of the algorithms. More detailed descriptions and further experimental results of this work can be found in [1].
机译:如果动态最短路径算法能够处理一次包含多个边更新的图形更改,则称为批处理算法。在本文中,我们专注于具有正边缘权重的有向图中单源最短路径的全动态批处理算法。我们对现有的单边和批处理算法进行了广泛的实验研究,其中包括大量的测试实例。我们进一步介绍了已存在的SWSF-FP算法的优化变体,其速度比SWSF-FP快15倍。本文令人惊讶的结果是算法的数据依赖程度达到了惊人的水平。这项工作的更详细的描述和进一步的实验结果可以在[1]中找到。

著录项

相似文献

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

客服邮箱:kefu@zhangqiaokeyan.com

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

  • 服务号