Fast Exact MultiConstraint Shortest Path Algorithms

  • Author(s) / Creator(s)
  • Technical report TR06-22. 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. | TRID-ID TR06-22

  • Date created
  • Subjects / Keywords
  • Type of Item
  • DOI
  • License
    Attribution 3.0 International