AN ALGORITHM FOR THE RANKING OF SHORTEST PATHS

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 (G1, G2, ..., G(K)) of networks is defined, such that G1 is the given network and its k-th shortest path is trivially determined from the shortest path in G(k). In essence, as soon as the shortest path in G(k) is determined it is excluded from G(k) in such a way that no new paths are formed and no mote paths are deleted. So, for each G(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 G(k+1), G(k+2), ..., G(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 10(4) nodes and 10(5) 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, comparative computational experiments are reported.