Finding k shortest simple paths in directed graphs: A node classification algorithm

We propose a new exact algorithm for enumerating k shortest simple paths in a directed graph with n nodes and m edges. The algorithm has a complexity of O ( k n ( m + n log n ) ) and follows the same process as Yen's deviation algorithm, but the candidate paths are computed more efficiently using a node classification technique. We first show that a candidate path can be separated by its deviation node as prefix and suffix. Our algorithm then classifies the nodes as red, yellow, and green. A node on the prefix is assigned a red color, a node that can reach t (the destination node) through a shortest path without visiting a red node is assigned a green color, and all other nodes are assigned a yellow color. We prove that when searching for the suffix of a candidate path, all green nodes can be bypassed, and we only need to apply Dijkstra's algorithm to find an all‐yellow‐node subpath. Since on average the number of yellow nodes is much smaller than n, the new algorithm has a much lower average‐case running time. Experiments on many types of networks demonstrate that the new algorithm performs significantly better than existing exact algorithms that have polynomial worst‐case complexity.