Shortest paths in almost acyclic graphs

This paper presents an algorithm for the shortest-path problem on a directed graph having arbitrary arc weights. One feature of the algorithm is its ability to exploit a certain type of structure. Two examples of this feature are highlighted. The first example is when the given graph is “almost” acy...

Full description

Saved in:
Bibliographic Details
Published in:Operations research letters 2000-11, Vol.27 (4), p.143-147
Main Author: Wagner, Donald K.
Format: Article
Language:English
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:This paper presents an algorithm for the shortest-path problem on a directed graph having arbitrary arc weights. One feature of the algorithm is its ability to exploit a certain type of structure. Two examples of this feature are highlighted. The first example is when the given graph is “almost” acyclic in the sense that there exists a small subset T of nodes, the deletion of which yields an acyclic graph. In this case, a version of the algorithm solves the shortest-path problem in O(| T| m) time; this bound is at least as good as the O( mn) time bound of Bellman (Quart. Appl. Math. 16 (1958) 87–90). The second example is when the weight vector is “almost” nonnegative in the sense that only a small subset F of arcs of the given graph have negative weight. In this case, the algorithm runs in O( min{|F|,n}(m+n log n)) time.
ISSN:0167-6377
1872-7468
DOI:10.1016/S0167-6377(00)00054-7