Premium
Shortest alternating path algorithms
Author(s) -
Brown J. R.
Publication year - 1974
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.3230040404
Subject(s) - shortest path problem , shortest path faster algorithm , yen's algorithm , widest path problem , matching (statistics) , path (computing) , k shortest path routing , undirected graph , algorithm , directed graph , constrained shortest path first , longest path problem , computer science , mathematics , graph , combinatorics , dijkstra's algorithm , statistics , programming language
The concept of an alternating path has been very useful in analyzing matching problems and has formed the basis for a number of matching algorithms. However, no techniques have been devised to find the shortest alternating path in a weighted graph. This paper defines different types of directed and undirected alternating paths, and shows how the problem of finding the shortest directed alternating path can be transformed into a problem of finding the shortest path in a directed graph. Utilizing this transformation, an efficient algorithm is developed for finding the shortest undirected alternating path. Computational experience is given. Extensions of the techniques in this paper to other types of alternating paths are discussed.