Efficient Shortest Path Simplex Algorithms

1 August 1990

journal article
Published by Institute for Operations Research and the Management Sciences (INFORMS) in Operations Research

Vol. 38 (4) , 624-628
https://doi.org/10.1287/opre.38.4.624

Abstract

We consider the specialization of the primal simplex algorithm to the problem of finding a tree of directed shortest paths from a given node to all other nodes in a network of n nodes or finding a directed cycle of negative length. Two efficient variants of this shortest path simplex algorithm are analyzed and shown to require at most (n − 1)(n − 2)/2 pivots and O(n³) time.

Keywords

SHORTEST PATHS
EFFICIENT
SHORTEST PATH SIMPLEX
PATH SIMPLEX ALGORITHMS
SUP

This publication has 0 references indexed in Scilit: