Premium
A decomposition algorithm for locating a shortest path between two nodes in a network
Author(s) -
Jarvis John J.,
Tufekci Suleyman
Publication year - 1982
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.3230120207
Subject(s) - shortest path problem , decomposition , algorithm , yen's algorithm , k shortest path routing , shortest path faster algorithm , path (computing) , constrained shortest path first , computer science , floyd–warshall algorithm , decomposition method (queueing theory) , dijkstra's algorithm , electronic circuit , mathematics , theoretical computer science , discrete mathematics , graph , ecology , electrical engineering , biology , engineering , programming language
A decomposition algorithm for locating a shortest path between two nodes of a network with circuits (directed cycles) and arbitrary arc distances (with the customary assumption of no negative circuits) is introduced. Unlike similar decomposition algorithms by Hu [12, 13], Yen [23], and Glover, Klingman, and Napier [10], this algorithm finds only the shortest distance between two specified nodes. Computational complexity of this algorithm is shown to be better than the previous decomposition algorithms.