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 | Controls and Control Theory | Electrical and Computer Engineering | Signal Processing | Theory and Algorithms
Posted with permission of 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 Stage Graph.
Proceedings of the XV International Conference On Systems Science, 15
Wrocław University of Technology Publishing House.