A FAST AND SIMPLE ALGORITHM FOR COMPUTING

We con~ider the problem of computing m shortest paths between a source node_s and a target node tin a stage graph. Polynomial time algorithms known to solve this problem use complicated data structures. This paper proposes a very simple algorithm for computing all m shortest paths in a stage graph efficiently. The proposed algorithm does not use any complicated data structure and can be implemented in a straightforward way by using only array data structure. This problem appears as a sub-problem for planning risk redl\ced multiple k-legged trajectories for aerial vehicles. 1