A genetic algorithm for finding the k shortest paths in a network

Abstract

Most of the multimedia applications require the k shortest paths during the communication between a single source and multiple destinations. This problem is known as multimedia multicast routing and has been proved to be NP-complete. The paper proposes a genetic algorithm to determine the k shortest paths with bandwidth constraints from a single source node to multiple destinations nodes. The algorithm uses the connection matrix of a given network, and the bandwidth of the links to obtain the k shortest paths. Some examples are provided to illustrate the effectiveness of this algorithm over conventional algorithms.

Keywords

• Computer networks
• Shortest paths
• Genetic algorithms
• Multimedia