Finding k shortest simple paths in directed graphs: A node classification algorithm
Author:
Abstract
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 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. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 6–17 2014Keywords
This publication has 19 references indexed in Scilit:
- Improved algorithms for the k simple shortest paths and the replacement paths problemsInformation Processing Letters, 2009
- Heuristic Methods for Delay Constrained Least Cost Routing Using$k$-Shortest-PathsIEEE Transactions on Automatic Control, 2006
- Near-shortest and K-shortest simple pathsNetworks, 2005
- Concepts of Exact QoS Routing AlgorithmsIEEE/ACM Transactions on Networking, 2004
- A new approach to all-pairs shortest paths on real-weighted graphsTheoretical Computer Science, 2004
- Undirected single-source shortest paths with positive integer weights in linear timeJournal of the ACM, 1999
- Fibonacci heaps and their uses in improved network optimization algorithmsJournal of the ACM, 1987
- Min-max heaps and generalized priority queuesCommunications of the ACM, 1986
- An efficient algorithm for K shortest simple pathsNetworks, 1982
- A note on two problems in connexion with graphsNumerische Mathematik, 1959