Premium
On algorithms for finding the k shortest paths in a network
Author(s) -
Shier D. R.
Publication year - 1979
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230090303
Subject(s) - shortest path problem , algorithm , computer science , k shortest path routing , floyd–warshall algorithm , yen's algorithm , grid , shortest path faster algorithm , dijkstra's algorithm , mathematics , theoretical computer science , graph , geometry
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.