Ripple-spreading Algorithm (RSA) is a relatively new, nature-inspired, multi-agent based method for path optimization. This paper demonstrates that by modifying the micro-level behaviors of nodes and ripples, RSA achieves good scalability for solving the k shortest paths problem (k−SPP). Initially, each node may generate k or more ripples to guarantee optimality. To improve computational efficiency for large-scale problems, we propose an approximate RSA (ARSA), where nodes generate no more than h ripples (1≤h Show more Show less