Premium
A dual simplex algorithm for finding all shortest paths
Author(s) -
Florian M.,
Nguyen S.,
Pallottino S.
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.3230110406
Subject(s) - shortest path problem , k shortest path routing , constrained shortest path first , yen's algorithm , shortest path faster algorithm , computer science , simplex algorithm , node (physics) , algorithm , dual (grammatical number) , simplex , euclidean shortest path , floyd–warshall algorithm , mathematical optimization , mathematics , dijkstra's algorithm , combinatorics , linear programming , theoretical computer science , graph , art , literature , structural engineering , engineering
We present an adaptation of the dual simplex algorithm, for computing all shortest paths on a network. Given a shortest path arborescence rooted at node r , the change of root to a new origin s , renders the arborescence rooted at r dual feasible and primal infeasible for the new problem. The adaptation of the dual simplex algorithm to compute the shortest paths from node s results in an algorithm which has the flavor of a label‐setting method. It generally does not require the examination of all the nodes of the network. We report some computational results with the method which indicate that it is at least as efficient as successive applications of a label‐setting or a label‐correcting shortest path algorithm.