Scholarlink

<p>In this paper we introduce a new algorithm for the <i>k</i>-<i>Shortest Simple Paths</i> (<InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12532_2025_276_Article_IEq1.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="13" /> </InlineMediaObject> <EquationSource Format="TEX">\(k\)</EquationSource> <EquationSource Format="MATHML"><math> <mi>k</mi> </math></EquationSource> </InlineEquation>-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick [<CitationRef CitationID="CR30">30</CitationRef>] that solves at most 2<i>k</i> instances of the <i>Second Shortest Simple Path</i> (<InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12532_2025_276_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">\(2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>-SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar <InlineEquation ID="IEq3"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="12532_2025_276_Article_IEq2.gif" Format="GIF" Height="14" Rendition="HTML" Resolution="72" Type="Linedraw" Width="10" /> </InlineMediaObject> <EquationSource Format="TEX">\(2\)</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>-SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.</p>

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

K-shortest simple paths using biobjective path search

  • 期刊论文

  • 发表日期：

    2025年2月13日

查看全文
  • Pedro Maristany de las Casas,
  • Antonio Sedeño-Noda,
  • Ralf Borndörfer,
  • Max Huneshagen

摘要

In this paper we introduce a new algorithm for the k-Shortest Simple Paths ( \(k\) k -SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roditty and Zwick [30] that solves at most 2k instances of the Second Shortest Simple Path ( \(2\) 2 -SSP) problem without specifying how this is done. We fill this gap using a novel approach: we turn the scalar \(2\) 2 -SSP into instances of the Biobjective Shortest Path problem. Our experiments on grid graphs and on road networks show that the new algorithm is very efficient in practice.