An efficient implementation of an algorithm for findingK shortest simple paths

DOI<88::AID-NET2>3.0.CO;2-1 10.1002/(SICI)1097-0037(199909)34:2<88::AID-NET2>3.0.CO;2-1zbMath0959.90060OpenAlexW1969097955MaRDI QIDQ4267389

Eleni Hadjiconstantinou, Nicos Christofides

Publication date: 2 May 2001

Full work available at URL: https://doi.org/10.1002/(sici)1097-0037(199909)34:2<88::aid-net2>3.0.co;2-1

zbMATH Keywords

undirected graph\(K\) shortest simple paths

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph theory (including graph drawing) in computer science (68R10)

Related Items

Finding \(K\) shortest looping paths in a traffic-light network ⋮ Enumerating \(K\) best paths in length order in DAGs ⋮ An integer optimality condition for column generation on zero-one linear programs ⋮ An efficient time and space \(K\) point-to-point shortest simple paths algorithm ⋮ Cutting stock problems and solution procedures ⋮ Lagrangian relaxation and enumeration for solving constrained shortest-path problems ⋮ Multicriteria path and tree problems: discussion on exact algorithms and applications ⋮ Finding \(K\) shortest looping paths with waiting time in a time--window network ⋮ Solving the \(k\)-shortest path problem with time windows in a time varying network ⋮ An Experimental Study on Approximating k Shortest Simple Paths ⋮ Distance confined path problem and separable integer programming ⋮ On the \(K\) shortest path trees problem ⋮ Diversification strategies in local search for a nonbifurcated network loading problem

Cites Work

• Unnamed Item
• Unnamed Item
• A Method for the Solution of the N th Best Path Problem
• Faster algorithms for the shortest path problem
• Computational experience with an algorithm for finding the k shortest paths in a network
• Efficient Algorithms for Shortest Paths in Sparse Networks

This page was built for publication: An efficient implementation of an algorithm for findingK shortest simple paths