Algebraic methods applied to shortest path and maximum flow problems in stochastic networks

We present an algebraic approach for computing the distribution of the length of a shortest s - t path, as well as the distribution of the capacity of a minimum s - t cut, in a network where the arc values (lengths and capacities) have known (discrete) probability distributions. For each problem, both exact and approximating algorithms are presented. These approximating algorithms are shown to yield upper and lower bounds on the distribution of interest. This approach likewise provides exact and bounding distributions on the maximum flow value in stochastic networks. We also obtain bounds on the expected shortest path length as well as the expected minimum cut capacity (and the expected maximum flow value). © 2012 Wiley Periodicals, Inc. NETWORKS, 2013