An efficient computational implementation of a path deletion K shortest paths algorithm and a new algorithm for the same problem are presented. In a path deletion K shortest paths algorithm a sequence {𝒢1,𝒢2,...,𝒢K} of networks is defined, such that 𝒢1 is the given network and its k-th shortest paith is trivially determined from the shortest path in 𝒢k. In essence, as soon as the shortest path in 𝒢k is determined it is excluded from 𝒢k in such a way that no new paths are formed and no more paths are deleted. So, for each 𝒢k, two procedures are executed: a shortest path algorithm and a path deletion algorithm. in the presented computational implementation, all the information resulting from the determination of the k-th shortest path is carried throughout 𝒢kÅ+1,𝒢kÅ+2,...,𝒢K. The new algorithm not only keeps this characteristic but also avoids the last K-1 executions of a shortest path algorithm, which results in a surprising and very substantial reduction in the execution time. In fact, for randomly generated networks with 104 nodes and 105 arcs, once the shortest path is determined, the new algorithm computes the next 100 shortest paths in times of the order of 10’-1 seconds. To illustrate the efficiency of this algorithm, compaative computational experiments are reported.
