.png){kind=icon}
返回
An Improved Multiobjective Shortest Path Algorithm
.png){kind=icon}
PRE
AI
DOI：10.1016/j.cor.2021.105424.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
We present a new label-setting algorithm for the Multiobjective Shortest Path (MOSP) problem that computes a minimum complete set of efficient paths for a given instance. The size of the priority queue used in the algorithm is bounded by the number of nodes in the input graph and extracted labels are guaranteed to be efficient. These properties allow us to give a tight output-sensitive running time bound for the new algorithm that can almost be expressed in terms of the running time of Dijkstra's algorithm for the Shortest Path problem. Hence, we suggest to call the algorithm Multiobjective Dijkstra Algorithm (MDA). The simplified label management in the MDA allows us to parallelize some subroutines. In our computational experiments, we compare the MDA and the classical label-setting MOSP algorithm by Martins, which we improved using new data structures and pruning techniques. On average, the MDA is 2 to 9 times faster on all used graph types. On some instances the speedup reaches an order of magnitude.
Keyword:
Multiobjective Shortest Path Problem
Network optimization
Output-sensitive multiobjective combinatorial problems
AI总结
对已上传原文的论文进行重点信息的提取，主要内容包括：简要概述、研究摘要、背景介绍、关键亮点、图文解析、展望与总结。
期刊
C
IF:
4.3
论文数:
6.5K
被引数:
1.8W
机构
引用论文
.png){kind=icon}
分享收藏
A swarm intelligence graph-based pathfinding algorithm (SIGPA) for multi-objective route planning
PREAI
分享收藏Multiobjective shortest path problems with lexicographic goal-based preferences具有基于词典目标的偏好的多目标最短路径问题
PREAI
分享收藏
查看更多内容