Fast Exact MultiConstraint Shortest Path Algorithms

摘要: QoS routing has been shown to be NP-hard. A recent study of its hardness shows that the “worst-case” may not occur in practice [13]. This suggests that there may exist fast exact algorithms for the multi-constraint shortest path (MCSP) problem, an instance of QoS routing. Search techniques such as A* and IDA* may solve hard problems exactly in polynomial time. In [14], we deploy the idea of iterative deepening search to design IDA* MCSP, and show its efficiency by extensive empirical study. In this paper, we show that for infeasible cases, IDA* MCSP may not be as efficient as A* Prune. This motivates us to design an algorithm that is efficient in both feasible and infeasible cases. We design an exact MCSP algorithm A* MCSP, which introduces the state notion and dominance relationship between states. Furthermore, we design an exact MCSP algorithm FringeMCSP. It can be regarded as an integration of IDA* MCSP and A* MCSP. Extensive empirical study shows that FringeMCSP has good performance in both feasible and infeasible cases; while IDA* MCSP still shows its superiority among the proposed MCSP algorithms in feasible cases. 1