Shortest paths in stochastic networks with ARC lengths having discrete distributions

In this work, we compute the distribution of L*, the length of a shortest (s, t) path, in a directed network G with a source node s and a sink node t and whose arc lengths are independent, nonnegative, integer valued random variables having finite support. We construct a discrete time Markov chain with a single absorbing state and associate costs with each transition such that the total cost incurred by this chain until absorption has the same distribution as does L*. We show that the transition probability matrix of this chain has an upper triangular structure and exploit this property to develop numerically stable algorithms for computing the distribution of L* and its moments. All the algorithms are recursive in nature and are illustrated by several examples.