Document Type
Article
Publication Date
2004
Publication Title
Systems Science
Volume
30
Issue
1
First page number:
91
Last page number:
97
Abstract
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.
Keywords
Computer algorithms
Disciplines
Applied Mathematics | Computer Engineering | Electrical and Computer Engineering | Electrical and Electronics | Signal Processing | Systems and Communications | Theory and Algorithms
Language
English
Permissions
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.
Repository Citation
Sherwood, M.,
Gewali, L. P.,
Selvaraj, H.,
Muthukumar, V.
(2004).
A Fast and Simple Algorithm for Computing M-shortest Paths in State Graph.
Systems Science, 30(1),
91-97.
https://digitalscholarship.unlv.edu/ece_fac_articles/297
Included in
Applied Mathematics Commons, Computer Engineering Commons, Electrical and Electronics Commons, Signal Processing Commons, Systems and Communications Commons, Theory and Algorithms Commons
Comments
Best copy available