DIMACS TR: 2005-04
Extending Dijkstra's Algorithm to Shortest Paths with Blocks
Authors: Jihui Zhao, Vladimir Gurvich and Leonid Khachiyan
ABSTRACT
We consider the problem of computing shortest paths in a directed
arc-weighted graph G=(V,A) in the presence of an adversary that
can block, for each vertex v, some subsets X(v) of the arcs
leaving v. We assume that if X(v) is an admissible blocking set of
arcs at v, then so is any subset of X(v). In other words, for each
vertex v, the hypergraph B(v) of all admissible blocks at v is an
independence system. We show that when the independence systems
B(v) are given by an arbitrary membership oracle, and the input
arc-weights are non-negative, the single-destination version of
the problem can be solved by a natural extension of Dijkstra's
algorithm in O(|A| log|V|) time and at most |A| monotonically
increasing blocking tests. We obtain better bounds for the special
case where each blocking system B(v) consists of all arc-sets X(v)
of given cardinality p(v), and also show that computing shortest
paths with blocks becomes NP-hard when the adversary can block a
given number of arcs arbitrarily distributed in the input graph.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2005/2005-04.ps.gz
DIMACS Home Page