Scholarlink

<p>The Shortest Path problem is fundamental for determining optimal routes in various applications. The Dynamic Shortest Path problem extends this concept to evolving graph structures. However, existing algorithms often fail to address decision-making complexities involving multiple objectives. In our previous work, we introduced the Multi-Objective Dynamic Shortest Path problem to address this gap. This paper presents the All-pairs Multi-objective Dynamic Shortest Path algorithm, offering a novel approach that combines a labeling-correcting method with the Optimistic Linear Support algorithm. This hybrid methodology enhances efficiency by minimizing redundant calculations during graph updates. Extensive testing demonstrates that our algorithm is over 3.22 times faster than baseline algorithms in producing Pareto solutions. This work advances techniques for multi-objective dynamic shortest paths and tackles challenges in evolving graph structures, paving the way for future research in this dynamic field.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

An efficient all-pairs approach for multi-objective dynamic shortest path problems

  • 期刊论文

  • 发表日期：

    2025年7月14日

查看全文
  • Juarez Machado da Silva,
  • Gabriel de Oliveira Ramos,
  • Jorge Luis Victória Barbosa

摘要

The Shortest Path problem is fundamental for determining optimal routes in various applications. The Dynamic Shortest Path problem extends this concept to evolving graph structures. However, existing algorithms often fail to address decision-making complexities involving multiple objectives. In our previous work, we introduced the Multi-Objective Dynamic Shortest Path problem to address this gap. This paper presents the All-pairs Multi-objective Dynamic Shortest Path algorithm, offering a novel approach that combines a labeling-correcting method with the Optimistic Linear Support algorithm. This hybrid methodology enhances efficiency by minimizing redundant calculations during graph updates. Extensive testing demonstrates that our algorithm is over 3.22 times faster than baseline algorithms in producing Pareto solutions. This work advances techniques for multi-objective dynamic shortest paths and tackles challenges in evolving graph structures, paving the way for future research in this dynamic field.