A Ripple-Spreading Algorithm for the k Shortest Paths Problem

Inspired by the natural ripple-spreading phenomenon that occurs on a water surface, this paper proposes a novel ripple-spreading algorithm (RSA) for the k shortest paths problem (k-SPP). In nature, a ripple spreads at a constant speed in all directions, and the node closest to the source will be the first to be reached. This very simple principle forms the foundation of the proposed RSA. By mimicking the natural ripple-spreading phenomenon, the new algorithm starts an initial ripple from the source, and initial ripple triggers new ripples at other nodes as it spreads out. A new ripple can also trigger ripples at nodes farther away, until the destination is reached by k ripples. Then the kth ripple that reaches the destination determines the kth shortest path. The comparative experimental results illustrate the effectiveness and efficiency of the proposed algorithm.