## Abstract

In this paper, 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, that can achieve 100% success ratio in finding the Delay Constrained Least Cost (DCLC) path with very low average computational complexity is proposed. The underlining concept is that since DIAHKP is a &-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 achiving 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.

Original language | English (US) |
---|---|

Pages | 1505-1509 |

Number of pages | 5 |

State | Published - Dec 1 2004 |

Event | GLOBECOM'04 - IEEE Global Telecommunications Conference - Dallas, TX, United States Duration: Nov 29 2004 → Dec 3 2004 |

### Other

Other | GLOBECOM'04 - IEEE Global Telecommunications Conference |
---|---|

Country/Territory | United States |

City | Dallas, TX |

Period | 11/29/04 → 12/3/04 |

## All Science Journal Classification (ASJC) codes

- Engineering(all)

## Keywords

- All hops k-shortest paths selection (AHKP)
- Delay constrained least cost (DCLC)
- NP-complete