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