Premium
A note on finding shortest path trees
Author(s) -
Kershenbaum Aaron
Publication year - 1981
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.3230110410
Subject(s) - shortest path problem , k shortest path routing , constrained shortest path first , path (computing) , yen's algorithm , mathematics , exponential function , longest path problem , combinatorics , shortest path faster algorithm , euclidean shortest path , computer science , polynomial , mathematical optimization , algorithm , discrete mathematics , dijkstra's algorithm , graph , mathematical analysis , programming language
Two shortest path algorithms are compared and it is shown that, while one outperforms the other in practice, the former's running time is exponential in the worst case while the latter's is polynomial. A procedure which constructs such worst case examples is given.