Achieving 100 success ratio in finding the delay constrained least cost path

摘要

We introduce an iterative all hops k-shortest paths (IAHKP) algorithm that is capable of iteratively computing all hops k-shortest path (AHKP) from a source to a destination. Based on IAHKP, a high performance algorithm, dual iterative all hops k-shortest paths (DIAHKP) algorithm, is proposed. It can achieve 100% success ratio in finding the delay constrained least cost (DCLC) path with very low average computational complexity. The underlying concept is that since DIAHKP is a k-shortest-paths-based solution to DCLC, implying that its computational complexity increases with k, we can minimize its computational complexity by adaptively minimizing k, while achieving 100% success ratio in finding the optimal feasible path. Through extensive analysis and simulations, we show that DIAHKP is highly effective and flexible. By setting a very small upper bound to k (k=1,2), DIAHKP still can achieve very satisfactory performance. With only an average computational complexity of twice that of the standard Bellman-Ford algorithm, DIAHKP achieves 100% success ratio in finding the optimal feasible path in the typical 32-node network.