We consider the problem of computing m shortest paths between a source node s and a target node t in 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 reduced multiple k-legged trajectories for aerial vehicles.
Applied Mathematics | Computer Engineering | Electrical and Computer Engineering | Electrical and Electronics | Signal Processing | Systems and Communications | Theory and Algorithms
Posted with permission from the Wrocław University of Technology, all rights reserved. You may download, display, print and reproduce this material in unaltered form (attaching a copy of this notice) for your personal, non-commercial use. The Wrocław University of Technology reserves the right to revoke such permission at any time.
Gewali, L. P.,
A Fast and Simple Algorithm for Computing m-shortest Paths in State Graph.
Systems Science, 30(1),