Review on K shortest paths algorithms
Xu Ta · Jisuanji gongcheng yu sheji · 2013
To promote the applications of K shortest paths algorithm (KSP) ,and to provide the relevant information for the further research on this algorithm,a review on the recent progress of KSP algorithms is given.According to restriction constrained on paths,the KSP problem can be classified into two types:the general KSP and the constrained loopless KSP.The basic ideas,research status and research progress for solving each type of two KSP problems are reviewed.Since KSP problem is very complex and the scale of the graph in application is very large,the efficiency has become an important indicator to evaluate a KSP algorithm.Time complexity is consequently a special concern in analyzing all kinds of KSP algorithms.Finally,future research directions of KSP are pointed out.The above work can give a valuable reference for multiple constraint shortest path problems.