Premium
Algorithms for the Weight Constrained Shortest Path Problem
Author(s) -
Dumitrescu Irina,
Boland Natashia
Publication year - 2001
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/1475-3995.00003
Subject(s) - shortest path problem , rounding , widest path problem , mathematical optimization , longest path problem , dynamic programming , path (computing) , theory of computation , relaxation (psychology) , graph , mathematics , computer science , algorithm , combinatorics , social psychology , programming language , operating system , psychology
Given a directed graph whose arcs have an associated cost, and associated weight, the weight constrained shortest path problem (WCSPP) consists of finding a least‐cost path between two specified nodes, such that the total weight along the path is less than a specified value. We will consider the case of the WCSPP defined on a graph without cycles. Even in this case, the problem is NP‐hard, unless all weights are equal or all costs are equal, however pseudopolynomial time algorithms are known. The WCSPP applies to a number of real‐world problems. Traditionally, dynamic programming approaches were most commonly used, but in recent times other methods have been developed, including exact approaches based on Lagrangean relaxation, and fully polynomial approximation schemes. We will review the area and present a new exact algorithm, based on scaling and rounding of weights.