Premium
Implementation of algorithms for K shortest loopless paths
Author(s) -
Perko Aarni
Publication year - 1986
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.3230160204
Subject(s) - shortest path problem , algorithm , k shortest path routing , computer science , path (computing) , shortest path faster algorithm , floyd–warshall algorithm , implementation , dijkstra's algorithm , mathematics , combinatorics , graph , programming language
Implementations of loopless k shortest path algorithms are examined. Efficient storage structures for a large number of paths are given. A fast algorithm for determining the shortest paths in Yen's method is developed. Timing experiments show that a hybrid of Clarke's and Yen's methods is generally the fastest, although not significantly. Using upper bounds for the lengths of paths essentially improves all methods.