Computing the Stochastic Shortest Path Length Between Two Vertices with Exponentially Distributed Edge Lengths in Graphs with Small Treewidth

摘要

In this paper, we propose an algorithm for the stochastic shortest path problem between two vertices in an undirected graph G. In the stochastic shortest path problem, the edge lengths are random variables, so shortest path lengths are also random variables. Our goal is to compute the distribution function of the stochastic shortest path length in G. Unlike the shortest path problem with fixed edge lengths which can be solved in polynomial time, we show that computing the exact distribution function of the stochastic shortest path length is #P-complete even if the edge lengths can take only two discrete values. In contrast, we show how to efficiently compute the distribution function B_G(x) of the stochastic shortest path length of G with exponentially distributed edge lengths. Our algorithm outputs the description of B{top}～G(x) as the sum of products of the polynomial of x and exponent of x. The running time of our algorithm is polynomial in the graph size, if the treewidth k of G are bounded by a constant.