The constrained shortest path problem

Y. P. Aneja and K. P. K. Nair

Naval Research Logistics Quarterly, 1978, vol. 25, issue 3, 549-555

Abstract: The shortest path problem between two specified nodes in a general network possesses the unimodularity property and, therefore, can be solved by efficient labelling algorithms. However, the introduction of an additional linear constraint would, in general, destroy this property and the existing algorithms are not applicable in this case. This paper presents a parametric approach for solving this problem. The algorithm presented would require, on the average, a number of iterations which is polynomially bounded. The similarity of this approach to that of the generalized Lagrange multiplier technique is demonstrated and a numerical example is presented.

Date: 1978
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
https://doi.org/10.1002/nav.3800250314

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:wly:navlog:v:25:y:1978:i:3:p:549-555

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().