SHORTEST PATHS IN STOCHASTIC NETWORKS WITH ARC LENGTHS HAVING DISCRETE-DISTRIBUTIONS

In this work, we compute the distribution of L, the length of a short est (s,t) path, in a directed network G with a source node s and a sin k node t and whose arc lengths are independent, nonnegative, integer v alued random variables having finite support. We construct a discrete time Markov chain with a single absorbing state and associate costs wi th each transition such that the total cost incurred by this chain unt il absorption has the same distribution as does L. We show that the t ransition probability matrix of this chain has an upper triangular str ucture and exploit this property to develop numerically stable algorit hms for computing the distribution of L and its moments. All the algo rithms are recursive in nature and are illustrated by several examples .