Document Type

Conference Proceeding


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.


Back propagation (Artificial intelligence); Computer algorithms; Open Shortest Path First (Computer network protocol)


Applied Mathematics | Controls and Control Theory | Electrical and Computer Engineering | Signal Processing | Theory and Algorithms


Conference held September 7 - 10, 2004, Warsaw, Poland

Best copy available


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.