• 主题
高级搜索  >
历史搜索 清空历史
首页> 外文会议>International Workshop on Experimental and Efficient Algorithms(WEA 2005); 20050510-13; Santorini Island(GR) >Partitioning Graphs to Speed Up Dijkstra's Algorithm
【24h】

Partitioning Graphs to Speed Up Dijkstra's Algorithm

机译：对图进行分区以加快Dijkstra的算法

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

摘要

In this paper, we consider Dijkstra's algorithm for the point-to-point shortest path problem in large and sparse graphs with a given layout. In [1], a method has been presented that uses a partitioning of the graph to perform a preprocessing which allows to speed-up Dijkstra's algorithm considerably. We present an experimental study that evaluates which partitioning methods are suited for this approach. In particular, we examine partitioning algorithms from computational geometry and compare their impact on the speed-up of the shortest-path algorithm. Using a suited partitioning algorithm speed-up factors of 500 and more were achieved. Furthermore, we present an extension of this speed-up technique to multiple levels of partitionings. With this multi-level variant, the same speed-up factors can be achieved with smaller space requirements. It can therefore be seen as a compression of the precomputed data that conserves the correctness of the computed shortest paths.
机译：在本文中，我们考虑在给定布局的大型和稀疏图中点对点最短路径问题的Dijkstra算法。在[1]中，提出了一种方法，该方法使用图的划分来执行预处理，从而可以大大加快Dijkstra算法的速度。我们提供了一项实验研究，评估了哪些分区方法适合该方法。特别是，我们从计算几何中检查划分算法，并比较它们对最短路径算法加速的影响。使用合适的分区算法，可以达到500甚至更高的加速因子。此外，我们提出了将该加速技术扩展到多个分区级别的方法。使用这种多级变体，可以以较小的空间需求实现相同的加速因子。因此，可以将其视为对预计算数据的压缩，从而保留了计算出的最短路径的正确性。

著录项

相似文献

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

客服邮箱：kefu@zhangqiaokeyan.com

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

  • 客服微信

  • 服务号