On algorithms for finding the k shortest paths in a network

TLDR

Strategies that efficiently solve shortest path problems underpin the algorithms discussed in this paper. The paper introduces several new algorithms for computing the k shortest paths in a network within a unified framework. A computational study evaluated the impact of different arc‑processing orders across generated grid, complete, and random networks. Two algorithms were identified as the most promising based on the study.

Abstract

Abstract This paper presents, within a unified framework, several new algorithms for computing k shortest paths in a network. These algorithms utilize strategies which have proved to be efficient in solving shortest path problems. In addition, a computational study was conducted to assess the effects of the different “arc processing” orders which are characteristic of each algorithm. Testing was performed using generated classes of moderately large grid, complete and random networks. Two particular algorithms emerge as the most promising among those evaluated.